[백준] 5557번 1학년

[적용한 알고리즘]

DP

 

[아이디어]

얼핏 보면 2^N 돌아야할 것 같아 불가능해보였다. 

그래서 한참 고민하다가, 상근이가 아는 숫자 x의 범위가 0<=x<=20 라는 걸 알고 더 고민했다. 

 

그래서

dp[i][j] = i 번째 숫자까지 봤을 때 j 를 만들 수 있는 경우의 수

0 <= i < N 이고,  0 <= j <= 20 이므로 시간 문제가 없다. 

 

입력 받은 숫자의 배열을 a[] 라고 하면,

dp[i][j] = dp[i - 1][j - a[i]] + dp[i - 1][j + a[i]] 이다 .

 

i - 1 번째 숫자에서 j 가 되기 위해서는

a[i]를 더해주는 경우가 있을 것이고,

a[i]를 빼주는 경우가 있을 것이기 때문이다. 

 

그래서 범위를 고려해 코드를 짤 수 있다. 

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

DP는 다채롭다. 힘든 과정인 것 같다. 

 

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

long long dp[101][21];

int main(){
    int N;
    scanf("%d", &N);
    N--;
    vector<int> a(N);
    for (int i = 0; i < N; i++){
        scanf("%d", &a[i]);
    }

    int goal;
    scanf("%d", &goal);

    dp[0][a[0]] = 1;

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

    printf("%lld\n", dp[N - 1][goal]);
    return 0;
}