13707 합분해 2

www.acmicpc.net/problem/13707

13707번: 합분해 2

합분해 2

합분해는 몇개의 수 중에 몇개를 선택하여 N의 값을 만드는 문제이다. 여기서 골치아팠던 점은 앞뒤가 바뀌거나 중복되는 숫자가 나와도 되는 점이었다. 

 

배열의 경우 의미하는 값은 dp[만들어야 하는 값][선택 개수]로 생각하고 풀었다. 

 

여기서 dp 점화식을 어떻게 만들 수 있을까? 

 

점화식에 앞서 N 까지의 수 중 선택하여 N을 만들 수 있는 방법은 몇개일까? 

 

우선 dp[1][K]의 경우 K개가 된다. 

dp[1][1] = {1, }

dp[1][2] = { {0, 1}, {1, 0} }

dp[1][3] = { {0, 0, 1}, {1, 0, 0}, {0, 1, 0} }

 

이런식으로 순서대로 1, 2, 3, 4 .... K 개가 된다. 

 

다음 N이 2부터는 아래의 식이 성립한다. 

 

dp[N][K] = dp[N-1][K] + dp[N][K-1];

 

아래의 식이 왜 성립하는 것일까? 

현재 위치에서 N-1 인 경우에는 1만 추가하면 아래의 조건을 만족하기 때문에 [1][3]의 3개를 사용한다. 

 

K-1의 경우에는 해당 값에서 0만 추가하면 되기 때문에 이조건을 만족한다. 따라서 합분해 1에 비해서 돌아야 하는 반복문이 늘어났어도 N^2만에 문제를 해결할 수 있기 때문에 시간 초과가 발생하지 않는다. 

 

위의 점화식을 사용하면 문제를 해결 할 수 있다. 

#include <cstdio>
#define ll long long

ll dp[5002][5002];

int main(){
	ll K, N;
	scanf("%lld %lld", &N, &K);

	for(int n = 1; n <= 5000; n++){
		for(int k = 1; k <= 5000; k++){
			if(n == 1){
				dp[n][k] = k;
			}else{
				dp[n][k] = (dp[n-1][k] + dp[n][k-1] ) % 1000000000;
				dp[n][k] %= 1000000000;
			}
		}
	}

	printf("%lld", dp[N][K]%1000000000);
}