취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5624번 문제인 좋은 수이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/5624 

각 i번째 수에 대하여, i보다 작은 인덱스를 가진 세 수의 합(중복 허용)으로 i를 만들 수 있는 수의 개수를 찾는 문제이다.

i보다 작은 인덱스를 가진 (두 수의 합)을 관리하고, i에서 (i보다 작은 인덱스를 가진 수)를 하나 뺀 값들이 (두 수의 합)의 집합에 속해있는지 판단하는 것으로 문제를 해결할 수 있다.

(두 수의 합)의 범위는 -20만 이상 20만 이하이므로, 각 수에 20만을 더해 크기 40만1의 배열로 접근이 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[5000];
int cnt2[400001]; // (실제 수 + 20만)

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int ans = 0;
	for (int i = 0; i < N; i++) {
		bool chk = 0;
		int num = arr[i];
		for (int j = 0; j < i; j++) {
			if (cnt2[num - arr[j] + 200000]) chk = 1;
		}
		for (int j = 0; j <= i; j++) cnt2[num + arr[j] + 200000] = 1;
		if (chk) ans++;
	}

	cout << ans;
}