백준 5624 좋은 수 :: 들짐승

<링크>

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

<풀이>

D앞의 수를 A,B,C라 하면
A+B+C=D 를 만족하면 D는 좋은 수이다.
같은 수를 여러번 더해도 된다. 수열의 수로 만들 수 있는 모든 조합을 세어보려면 
1 2 3 5 7 10
1 + 1 + 1
1 + 1 + 2
1 + 1 + 3
,,,
10 + 10 + 10

일케 해야되는데 N^3이 걸린다. N이 5000이라 시간초과가 뜰 것이다.

A+B=D-C를 이용하면 된다.
D를 하나 찝어서 D의 앞의 수(C)를 다 빼본다.
그 후 A+B가 지금까지 나온적이 있었냐만 보면 된다.
A와 B는 AA가 돼도 되고 AB, BB가 되어도 되며 C가 섞여도 된다. 왜냐면 같은 수를 여러번 더해도 되기 때문이다. 그 말은 D의 앞에 있는 두 수로 만든 조합이면 뭐든 상관없다는 뜻이다.

예를들면)
1 2 3 4 5 6 7
D=6, C=1 // 6-1 = 5 -> 5를 6 앞의 어떤 두 수로 만들어도 상관없다. 1이 섞여도 된다.

5라는 조합이 나왔었는지 확인한 뒤, 있으면 정답을 늘려주고 바로 break를 해서 나와줘야 한다. 중복해서 셀 수 있기 때문이다.

6-1,6-2,6-3,6-4,6-5가 끝난 뒤에는
(D=7)도 똑같은 방식으로 확인해야하는데
그럼 현재의 (D=6)는 새로 올 (D=7)의 앞의 수가 되기 때문에
현재의 (D=6)으로 만들 수 있는 조합을 추가해줘야한다.

현재의 D=6일때
11,12,13,14,15
22,23,24,25
33,34,35
44,45
55 의 조합이 이미 체크되어있었으므로 확인 할 수 있었던 것이다.

6이 새로 추가됐을때
16,26,36,46,56,66 을 추가해줘야 다음번부터 체크할 수 있다.
따라서 맨앞부터 현재의D까지 생기는 조합을 새로 추가해준다.

처음에는 set으로 구현했다가 시간초과가 떴다. 
set에서 있냐 없냐는 판단할 때 logN이 걸리는데 그럼 결국 N^2 * logN = 2억이 넘기 때문에 시간 초과가 뜬 것 같다.
메모리를 좀 빌려와서 배열에 체크하는 방식으로 바꾸니깐 통과되었다.
[D-C] 가 1이면 지금까지 나왔던 조합이라 생각한다.
이 때 D-C의 범위는 곧 A+B의 범위이고
-200000~200000이다.
그대로 오른쪽으로 20만 옮겨서 구현했다.

<소스코드>

#include<set>
#include<stdio.h>
using namespace std;
int a[5000];
int is[500000];
set<int> s;
int main()
{
    int N;
    int ans = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", a + i);
    
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int D_C = a[i] - a[j];
            if (is[D_C+200000])
            {
                ++ans;
                break;
            }
        }
        for (int j = 0; j <= i; ++j)
            is[a[i] + a[j] + 200000] = 1;
    }
    printf("%d", ans);
}