중복 조합

n 종류의 물건이 있고 i번째 물건은 ai개 있습니다. 다른 종류의 물건끼리는 구별 가능합니다만, 같은 종류의 물건끼리는 구별 불가능합니다. 이들 물건 중에 m개를 골라 조합해 총수를 구하고M으로 나눈 나머지를 구하세요.

 

위의 문제는 다른 종류의 물건끼리는 구별이 가능하므로 아래와같이 점화식을 세울 수 있다.

dp[i + 1][j] = i까지의 숫자를 이용하여 j개를 조합할 수 있는 총 갯수

 

i - 1번째 까지의 숫자를 이용하여 j - k개를 고르고 나머지 k개를 i번째 수에서 고르는 경우를 모두 더하면 i까지를 이용하여 j개를 고르는 모든 조합을 구할 수있다.

dp[i + 1][j] = dp[i][j - k] (0 <= k <= min(a[i], j))

 

위와 같은 점화식은 O(n * M^2)의 시간 복잡도를 갖는다. 좀더 최소화 하는 방법으로 간단하게 점화식을 변경할 수 있다.

dp[i][j - k] (0 <= k <= min(a[i], j)) = dp[i][j] + dp[i][j - 1] + dp[i][j - 2] + ... +

dp[i][0](or dp[i][j - a[i]])

여기서 k의 범위를 하나 줄이면 다음과 같이 점화식이 변한다

dp[i][j - 1 - k] (0 <= k <= min(a[i], j - 1)) = dp[i][j - 1] + dp[i][j - 2] + dp[i][j - 3] + ... + dp[i][j - a[i]] + dp[i][0](or dp[i][j - 1 - a[i]))

 

dp[i][j - k] (0 <= k <= min(a[i], j)) = dp[i][j - 1 - k] (0 <= k <= min(a[i], j - 1)) + dp[i][j] - dp[i][j - 1 - a[i]]

= dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - a[i]] = dp[i + 1][j]

이 같은 점화식의 변형으로 문제를 O(nm)만에 해결 가능하다.

문제를 해결하는 코드는 아래와 같다.

 

int dp[MAX_N + 1][MAX_M + 1];

 

int main(){

  for(int i = 0; i < n; ++i)

    dp[i][0] = 1;

  for(int i = 0; i < n; ++i)

    for(int j = 1; j <= m; ++j){

      if(j - 1 - a[i] >= 0)

        dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 -            a[i]];

      else

        dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j];

  cout << dp[n][m] << endl;

}