BOJ)5624 좋은 수

문제:icpc.me/5624

좋은 수의 조건은 나보다 먼저 들어온 수 i, j ,k 의 합이 나와 같은 경우가 존재하는 경우이다.

우리는 이 수식을 i+j+k=x 로 생각할 수 있고 이 수식을 i+j=x-k로 바꿔 생각할 수 있다.

그러면 우리는 x를 받기전에 들어온 모든 수들의 합의 셋(i+j)들을 배열로 저장하여 O(1)만에 존재하는지 확인할 수 있다.

고로 모든 x-k에 대하여 같은 i+j가 존재하는지 확인해 준다면 O(N^2)에 문제를 해결할 수 있다.

#include <cstdio>
#include <algorithm>
#define mid 200000
using namespace std;
int a[5010], n, b[400040], res;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        int here = a[i];
        for (int j = 0; j < i; j++) {
            if (b[here - a[j] + mid]) {
                res++;
                break;
            }
        }
        for (int j = 0; j <= i; j++)
            b[here + a[j] + mid] = 1;
    }
    printf("%d\n", res);
    return 0;
}