[백준] 21636 : Multiple Subject Lessons

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

N=3, K=2

문제 분석

 문제는 n과 k가 주어졌을 때 합이 N이 되게끔 숫자를 분할하고 각 숫자별로 k개의 색 중 하나를 배정했을 때 나올 수 있는 경우의 수를 구하는 문제이다. 단순히 합이 N이 되게끔 숫자를 분할하고 각 숫자별 개수에 따라 k개의 색을 배분하는 케이스를 구하면 된다.

 합이 N이 되는 숫자의 조합은 단순히 DP를 통해서 조합의 수는 구할 수있지만 실제 각 숫자별 개수가 필요하여 다른 방식을 사용해야 한다. 브루트 포스로 모든 케이스를 고려하여 구해도 된다. N은 최대 17이므로 분할가능한 케이스는 순서를 고려해도 $2^{16} \approx 64000$의 크기를 가진다. 다만, 중복을 제거해야 하므로 백트래킹 방식을 사용하여 가장 큰 수부터 내림차순으로 조합을 가지도록 코드를 설계했다. 

 각 숫자별 개수에따라 k개의 색을 배분하는 케이스는 DP를 구하여 계산이 가능하다. S개의 동일한 숫자를 k개의 색깔로 색칠하는 경우의 수를 DP [S, K]라 두었을 때  DP [S, K]는 아래와 같이 K번째 색상을 사용하지 않은 경우부터 K번쨰 색상을 S개 사용한 경우까지의 합으로 표현가능하다. 또한,  K번째 색상을 하나만 사용한 경우 부터 S개 사용한 경우까지의 합은 DP[S-1,K]와 같으므로 2번째식과 같이 간략화된 점화식을 통해 계산이 가능하다.

DP [S, K] = DP [S, K-1]+DP [S-1, K-1]+DP [S-2, K-1]+...+DP [S-S, K-1]
DP [S, K] = DP [S, K-1]+DP [S-1, K]

문제 해결 전략

 1번째로 GetPartiotionCase를 통해 숫자의 조합들을 구한다. 2번째로 각 조합별로 숫자별 개수를 세는 코드를 통해 partionCount를 얻는다. 마지막으로 CountColoringCase k개의 색상을 칠하는 것을 고려한 경우의 수를 구해 주고 이를 모든 조합에 적용하고 더해주어 최종적인 값을 얻는다. 

코드

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

long long n,k;

//1. n의 분할 (브루트 포스로접근)
//어차피 17개라 최대 2^16=64000의 분할 케이스
// 단순 가능한 분할의 개수가아니라 내부 구성을 고려해야되서 DP안 씀
//2. 분할된 S개를 K 개의 색깔놀이 계산 DP 연산
//DP[S,K] = DP[S,K-1]+DP[S-1,K-1]+DP[S-2,K-1]+...+DP[S-S,K-1]
//DP[S,K] = DP[S,K-1]+DP[S-1,K]

void GetPartitionCase(int N, int maxVal, vector<int> currentPartition,vector<vector<int>>& outResult){
    if (maxVal!=-1) {
        currentPartition.push_back(maxVal);
    }
    else{
        maxVal=N;
    }

    if (N==0) {
        outResult.push_back(currentPartition);
        return;
    }

    for (int i = min(maxVal,N); i >0 ; i--)
    {
        if (N>=i) GetPartitionCase(N-i, i, currentPartition, outResult);
    }
}

long long CountColoringCase(const long long coloringDP[18][18], const vector<int>& divisionNum, int k){
    long long res(1);
    for (auto num : divisionNum) res*=coloringDP[num][k];
    return res;
}

int main()
{
    cin >> n >> k;
    vector<vector<int>> partitions;
    long long coloringDP[18][18];
    long long result(0);

    for (size_t i = 1; i < 18; i++)
    {
        for (size_t j = 1; j < 18; j++)
        {
            if (i==1 || j==1) {
                coloringDP[i][j]=j;
                continue;
            }
            coloringDP[i][j]=coloringDP[i][j-1]+coloringDP[i-1][j];
        }
        
    }
    

    GetPartitionCase(n,-1,vector<int>(),partitions);
    for(auto partition : partitions){
        vector<int> partitionCount;
        int temp(-1);
        for(auto part : partition){
            if (temp!=part){
                partitionCount.push_back(1);
                temp=part;
            }
            else{
                partitionCount[partitionCount.size()-1]+=1;
            }
        }

        result+=CountColoringCase(coloringDP, partitionCount,k);
    }
    cout << result << "\n";
}