[DP]집합의 분할

인적성을 공부하는 친구가 단체 톡방에 노가다 말고 순열공식이 없냐고 물어봤다. 해당 문제는 자연수의 분할 문제이다. 문득 작년 알고리즘 경진대회에서 집합의 분할 / 자연수의 분할 문제를 못풀어서 부들부들했던 기억이 새록새록 났다. 동적 계획법(DP)문제인 건 알았지만 끝내 점화식을 세우지 못했다. 

 

1. 집합의 분할(partion of set)이란?

 위의 문제는 같은 종류의 쿠키 10개를 나누는 문제이다. 하지만 집합의 분할은 서로 다른 쿠키 10개를 나누는 문제와 같다. 예를 들어 {1,2,3}은 다음과 같이 총 5개의 분할이 생긴다. 

1|2|3  

1|2,3

1,2|,3

2|1,3

1,2,3 

이를 기호로 표현하면 S(n,k) n개의 원소를 k개의 집합으로 분류한 수를 의미한다. 저 위의 집합을 기호로 표현하면 

S(3,1) = 1 , S(3,2) = 3 , S(3,3) = 1 이다. 

 

2. 집합의 분할의 수의 성질

 - S(n,1) = 1 , S(n,n) = 1 // 자명하다.

 - S(n,k) = S(n-1, k-1) + kS(n-1, k) 

S(n-1, k-1) // 특정 원소가 독립적으로 1개가 생기는 경우 .

kS(n-1, k) // 특정 원소가 다른 원소와 같이 있는 경우.

즉 이 두가지 경우의 합으로 이루어진다.

 

3. 코드

#include "pch.h"
#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int memo[101][101];
int N, K;

int main()
{
	// total num, set num
	cin >> N >> K;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			if (j == 1 || j == i) {
				memo[i][j] = 1;
			}
			else {
            // 점화식
				memo[i][j] = memo[i - 1][j - 1] + j * memo[i - 1][j];
			}
		}
	}
	cout << memo[N][K];
}