[백준 2225][DP][C++] 합분해

 

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

2225번: 합분해

dp Table을 그리면 쉽게 점화식을 구할 수 있는 문제였다.

dp Table의 각 칸은 모든 경우의 수를 직접 써내려가며 구해도 되지만, 순열공식을 통해 더 빠르게 구할 수 있다.

예를 들어, n=5, k=3 일 때 각 조합의 경우의 순열의 개수는,

(3,0,0) -> 3!/2! = 3

(2,1,0) -> 3! = 6

(1,1,1) -> 3!/3! = 1

따라서, 3+6+1 = 10

 

위와 같이 n=8, k=4 까지 구한 dp Table은,

k\n	1	2	3	4	5	6	7	8
1	1	1	1	1	1	1	1	1
2	2	3	4	5	6	7	8	9
3	3	6	10	15	21	28	36	45
4	4	10	20	35	56	84	120	165

위와 같고, 위 테이블을 dp라는 이름의 배열이라 할 때,

dp[i][1] = 1, dp[1][j] = j 임을 볼 수 있고 또한 dp[i][j] = dp[i-1][j]+dp[i][j+1] 임을 볼 수 있다.

 

점화식을 구했으므로, 구현은 간단하게 할 수 있다.

 #include<iostream>
using namespace std;

int main(){
	int n,k,arr[201][201]={};
	cin>>n>>k;
	for(int i=1; i<=200; i++){
		arr[i][1]=i;
		arr[1][i]=1;
	}
	for(int j=2; j<=n; j++){
		for(int i=2; i<=k; i++){
			arr[i][j]=(arr[i][j-1]+arr[i-1][j])%1000000000;
		}
	}
	cout<<arr[k][n]<<endl;
}

 

*풀이 및 코드에 대한 지적은 모두 기쁘게 받습니다!!