[DP] 백준 5557번 - 1학년

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

5557번: 1학년

전형적인 DP 문제였습니다.

배열의 성격을 잘 결정하고, 초기값을 잘 결정해준 뒤 점화식을 세워 코딩하면 되는 문제입니다.

 

dp[i][j]를 설정하였는데 이는

'i번째 까지 숫자를 활용해 만든 수가 j가 되는 경우의 수'를 저장하는 배열입니다.

 

초기값은 

dp[0][number[0]] = 1로 설정해 줄 수 있습니다.

즉, 0번째 까지 숫자를 활용해 만든 수가 number[0]인 경우의 수로, 이는 곧 한 가지 경우밖에 없습니다.

 

다음으로 점화식은

이전숫자까지 활용해 j를 만든 경우의 수가 존재한다했을 때, 현재의 수 number[i]를 더한 결과가 20이하인 경우와 뺀 결과가 0 이상인 경우를 생각해주면 됩니다.

즉, for(int i=0; i<N-1; i++)

      for(int j=0; j<21; j++) 루프를 돌 때

dp[i-1][j]가 존재한다면, 그리고

  1. j + number[i] <= 20이라면 dp[i][j+number[i]] += dp[i-1][j]; 를 해줄 수 있으며,

  2. j - number[i] >= 0이라면 dp[i][j-number[i]] += dp[i-1][j];를 해줄 수 있습니다.

 

최종적으로 N-2까지 활용한 결과가 number[N-1]이 되는 경우의 수를 구하는 것이므로 

dp[N-2][number[N-1]]을 출력하면 됩니다. 이 때, dp배열의 자료형은 long long으로 설정했습니다.

 

아래는 코드입니다.

#include <stdio.h>
#pragma warning(disable:4996)
int numbers[100];
long long dp[100][21];
int main(){
    int N;
    for (int i = 0; i < 100; i++){
        numbers[i] = 0;
        for (int j = 0; j < 21; j++){
            dp[i][j] = 0;
        }
    }
    scanf("%d", &N);
    for (int i = 0; i < N; i++){
        scanf("%d", &numbers[i]);
    }
    dp[0][numbers[0]] = 1;
    // dp[x][y] : x번째 까지 요소를 갖고 y를 만드는 경우의 수.
 
    for (int i = 1; i <= N - 2; i++){
        for (int j = 0; j <= 20; j++){
            if (dp[i - 1][j]){
                if (j + numbers[i] <= 20) dp[i][j + numbers[i]] += dp[i - 1][j]; 
                // 이전에 만든 숫자 j에다가 현재 숫자 numbers[i]를 더해 20이하면 
                // 현재 i번째 까지 요소를 갖고 j+numbers[i]를 만드는 경우의 수는
                // 이전까지 j를 만든 경우의 수를 더해주는 것과 같다.
                if (j - numbers[i] >= 0) dp[i][j - numbers[i]] += dp[i - 1][j];
            }
        }
    }
    printf("%lld", dp[N - 2][numbers[N - 1]]);
    return 0;
}