[백준][2092번][DP] 집합의 개수

집합의 개수 

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

<코드>

#include <stdio.h>
 
int dp[210][4010];
int numbers[210];
 
int main(void){
 
    int T, A, S, B;
    int total = 0;
    scanf("%d %d %d %d", &T, &A, &S, &B);
    dp[0][0] = 1;
    
 
    for (int i = 0; i < A; i++)
    {
        int temp;
        scanf("%d", &temp);
        numbers[temp]++;
    }
 
    for (int i = 1; i <= T; i++)
    {
        // 숫자 하나로만 만들 경우 추가
        for (int k = 0; k <= numbers[i]; k++){
            dp[i][k] += 1;
        }
        
        for (int j = 1; j <= A; j++){
            // 전에 있는 숫자들의 조합 그대로 가져옴
            dp[i][j] += dp[i - 1][j];
            // 새로운 숫자들과 지난번에 있는 숫자들로 추가해서 만듬
            for (int k = 1; k <= numbers[i]; k++){
                if (j - k>0){
                    dp[i][j] += dp[i - 1][j - k];
                    dp[i][j] %=1000000;
                }
            }
        }
    }
    
    for (int i = S; i <= B; i++)
        total += dp[T][i] % 1000000;
 
    printf("%d\n", total % 1000000);
 
 
    return 0;
}

<문제 푼 요령>

1. 다이나믹 프로그래밍 이다.

2. 이전의 조합들을 이용하여서 새로운 조합을 만든다.

3. DP 테이블은 2차원 배열로 만드는데 여기서 행은 1~200까지의 숫자들 열은 K로 생각하고 만들기 때문에 최대 DP 배열의 크기는 200 X 4000이 된다.

4. 각 행마다 새롭게 만들어지는 조합들로 이루어진다. 즉 이전 행들은 다 이전에 만들어지는 조합인 것이다. 여기서 중요한 것은 각 숫자의 갯수를 카운트하는게 중요하다. 

5. 새로운 조합을 만드는 방법의 3가지 방법으로 구분이 된다. 

(1) 예를 들어 5가 4개 있으면 5, 55, 555, 5555 이런식으로 각 자리의 개수가 각각 1개씩이다. 즉 4자리까지 1씩 추가한다.

(2) 그 후 이전에 만들어져 있는 조합들을 그대로 가져온다.

(3) 이 전의 조합들과 새로 만들어진 5, 55,555,5555로 만들어지는 조합을 새로 만들어서 추가한다. 경우의 수로 사실 곱해야 하지만 각각 자리의 새로생기는 숫자는 최대 1이기 때문에 1 X 이전의 갯수는 = 이전의 갯수기 때문에 이전에꺼만 가져오면 된다.