[백준] 5624번: 좋은 수 - C++

문제

정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다)

수열이 주어졌을 때, 총 몇 개의 수가 좋은 수 일까?

 

입력

첫째 줄에 수열 A의 크기 N이 주어진다. (1 ≤ N ≤ 5000) 둘째 줄에는 수열 A의 각 숫자가 공백으로 구분되어 주어진다. (-100,000 ≤ A_i ≤ 100,000)

 

출력

첫째 줄에 좋은 수의 개수를 출력한다.

---

오랜만에 풀어보았던 다이나믹 프로그래밍 문제였다. 풀어본지도 오래됐거니와, 난이도 있는 문제라 스스로 생각해내기가 너무 어려워서 결국 구글의 힘을 빌렸다ㅠㅠ

핵심적인 식은 x + y + z = n 이므로, 정리하면 x + y = n - z 라는 것.

이를 이용하여 방문되었는지 확인하는 visited 배열에서 (x + y)값에는 방문했다고 표시하고, (n - z)가 있다면 좋은 수로 체크해준다.

200,000을 더하는 이유는 수의 범위가 -100000에서 100000이므로, 가장 작은 수 -100000이 두번 더했을 때 0이 되도록 인덱스 범위를 벗어나지 않게 보정해주기 위해서이다.

 

코드

#include <cstdio>
#define MAX 5000

int A[MAX];
bool visited[400001] = { false };

int DP(int num);

int main(void) {
    int N;
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    printf("%d\n", DP(N));
    return 0;
}

int DP(int num) {
    int result = 0;

    for(int i = 0; i < num; i++) {
        for(int j = 0; j < i; j++) {
            if(visited[A[i] - A[j] + 200000]) {
                result++;
                break;
            }
        }

        for(int j = 0; j <= i; j++) {
            visited[A[i] + A[j] + 200000] = true;
        }
    }
    return result;
}