[백준] 2293-동전 1

전형적인 dp문제입니다.

 

 

점화식을 고려할때 머리로 연상되지 않습니다.

표를 그리며 차근차근 풀어나가보았습니다.  

예시입력에 경우
        k   0   1   2   3   4   5   6   7   8   9   10
c(0)    [0] 1   0   0   0   0   0   0   0   0   0   0
c(1)    [1] 1   1   1   1   1   1   1   1   1   1   1
c(2)    [2] 1   1   2   2   3   3   4   4   5   5   6
c(3)    [5] 1   1   2   2   3   4   5   6   7   8   10

1의 경우에는 모두 1가지 경우의수를 가지게 되고

2를 포함할 경우 2의 배수마다 경우가 한가지씩 증가하는 것을 확인 할 수 있었습니다.

즉, 2를 포함할 때 1의 경우+ DP[N-2] + 1 의 경우가 됨을 확인할 수 있습니다. 

5를 포함할 때에는 (1의경우가 포함된) 2의 경우 + DP[N-5] + 1 이 됨을 확인할 수 있었습니다. 

 

즉 점화식을 나타내면 

for (int i = 0; i < n; i++) {
		dp[i][0] = 1;
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num&& i>0) dp[i][j] = dp[i][j - num] + dp[i - 1][j];
			else if(i>0) dp[i][j] = dp[i - 1][j];
			else if (j >= num) dp[0][j] = dp[i][j - num];
		}

	}

네 메모리 초과입니다.. :) ㅋㅋㅋ

문제조건이 4MB였네요. 

 

int형은 4byte이고 n=100까지, k=10000까지이니 dp 2차원 배열은 4000,000byte= 4000kbyte = 4mbyte이므로 메모리 초과가 나는것입니다. 직관적으로 점화식이 변화하는것을 확인했기때문에 dp[101][10001] 를 dp[10001]로 줄여보겠습니다. 

	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num] ;
		}
	}

전체코드입니다. 

 

#include <iostream>

using namespace std;

int dp[10001] = { 0 };
int n = 0, k = 0;
int arr[100] = { 0 };
int result = 0;

int main() {

	cin >> n >> k;
	
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		int num = arr[i];
		for (int j = 1; j <= k; j++) {
			if (j >= num) dp[j] += dp[j - num];
		}

	}
	cout << dp[k] << endl;
}