백준 5557 1학년 (C++)

5557번: 1학년

dp를 이용한 문제이다. 단순 완전 탐색으로 문제를 풀게 되면 겹치는 구간이 많이 생겨 시간 낭비가 생긴다. 예를 들어 5,2,2라고 할 때, 5-2+2 와 5+2-2 의 값은 같은데 두번 탐색하게 되고 이것이 반복되면 시간 초과가 일어난다. 그래서 dp를 이용해 해당 숫자에 해당하는 경우의 수를 저장해주었다. 반복문을 돌며 0 이상 20 이하에 해당하는 수에 도달하면 이전 경우의 수를 더해주었고 목표값에 저장된 경우의 수를 출력해주었다.
생각보다 아이디어가 안떠오른 문제였다. dp 문제를 더 풀어봐야 겠다.

#include <iostream>

using namespace std;

int N;
int A[101];
long long dp[101][21];

void solution() {
    dp[1][A[1]] = 1;

    for (int i = 2; i < N; i++) {
        for (int j = 0; j <= 20; j++) {
            if (dp[i - 1][j] == 0) continue;

            if (j - A[i] >= 0) {
                dp[i][j - A[i]] += dp[i - 1][j];
            }
            if (j + A[i] <= 20) {
                dp[i][j + A[i]] += dp[i - 1][j];
            }
        }
    }

    cout << dp[N - 1][A[N]] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

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

    solution();

    return 0;
}