백준 2092 - 집합의 개수

icpc.me/2092

 

1 이상 T 이하의 값을 가진 수 A개가 주어지면 개중에 K개 뽑아서 집합을 만들 때 각 집합의 원소 개수가 S 이상 B 이하인 집합의 개수를 구하는 문제이다. (순서가 다른 것은 같은 것으로 친다.)

 

이 문제는 푼 사람이 얼마 안되지만 부분집합 개수와 관련된 연산을 하는 문제는 dp의 주요 유형중 하나이다.

Solution

일단 A개의 원소들을 각 수가 몇 개 존재하는지 기록하자. 구현에서는 배열을 사용하였다.

 

dp 테이블은 이차원으로 설계한다.

 

dp[n][k] -> n 이하의 값을 가진 수 중에서 k개를 선택해 집합을 생성하는 경우의 수

 

이때 공집합을 인정하여 dp[0][0] = 1이다.

 

1부터 T까지 반복문을 돌면서 단일 숫자로 집합을 생성하는 경우(ex {5}, {5, 5}...)를 하나씩 추가해준다. (공집합도 추가하는 것을 빠트리지 말자)

 

그 후 0부터 T까지 반복문을 돌면서 다음 연산을 수행한다.

 

1. i번째라고 하면 i - 1번째에서 계산된 경우의 수를 포함해야 하므로 이를 더해준다.

 

2. 0부터 A까지 반복문을 통해 해당 수를 j개 사용하여 집합이 만들어지는 경우의 수를 계산하면 되는데 이는 이미 계산된 i - 1까지의 수를 통해 만들 수 있는 집합에서 i를 k개 사용하여 집합이 만들어지는 경우의 수를 더해주면 된다.

 

전체 코드

#include <bits/stdc++.h>
 
#define mod 1000000
 
using namespace std;
 
int t, a, s, b;
int mp[201];
int dp[201][4001];
int res;
 
int main()
{
    dp[0][0] = 1;
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> t >> a >> s >> b;
 
    for (int i = 0; i < a; ++i)
    {
        int x;
        cin >> x;
        ++mp[x];
    }
 
    for (int i = 1; i <= t; ++i)
    {
        for (int k = 0; k <= mp[i]; ++k)
            ++dp[i][k];
        
        for (int j = 0; j <= a; ++j)
        {
            dp[i][j] += dp[i - 1][j];
 
            for (int k = 1; k <= mp[i]; ++k)
                if (j - k > 0)
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
        }
    }
 
    for (int i = s; i <= b; ++i)
        res = (res + dp[t][i]) % mod;
    cout << res;
}

 

이것에 기초한 아주 어려운 문제가 있다. 작성자는 링크에 게재된 문제를 풀기 위해 기초를 공부하고 있다.