[백준/C++] 2293 동전 1 (G5)

유형	난이도	완료일	링크	특이사항
DP/냅색	골드5	23/03/15	https://www.acmicpc.net/problem/2293

 

 

틀린 코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10001][101];

int coin[100];

int Recursion(int K, int idx)
{
	if(idx == 0)
	{
		if(K%coin[0]==0)
		{
//cout << " K: "<<K<<" idx: "<<idx<<" return +1\\n";
			return 1;	
		}
		
		else
		{
//cout << " K: "<<K<<" idx: "<<idx<<"return +0\\n";
			return 0;
		}
			
	}
	else if(K == 0)
	{
//cout << " K: "<<K<<" idx: "<<idx<<"return +1\\n";
		return 1;
	}
		
	
	
	if(dp[K][idx]!=-1)
	{
//cout << " K: "<<K <<" idx: "<<idx<< " Existing dp : "<< dp[K][idx] << "\\n";
		return dp[K][idx];
	}
	
	else
	{
		int sum = 0;
		for(int i=K/coin[idx]; i>=0; i--)
		{
			sum += Recursion(K-i*coin[idx],idx-1);
		}

		dp[K][idx] = sum;	
		
//cout << " K: "<<K <<" idx: "<<idx<< " New dp : "<< dp[K][idx] << "\\n";
//		return dp[K][idx];
		return sum;
	}
		
}

int main(void)
{
	for(int i= 0;i<=10000; i++)
	{
		for(int j =0;j<=100;j++)
			dp[i][j]=-1;
	}
	int n,k;
	cin >> n >> k;
	
	for(int i=0; i<n; i++)
		cin >> coin[i];
	
	sort(coin, coin+n);
	
	cout << Recursion(k, n-1);
	
}

맞을 거라고 기대했지만 메모리 제한이 4MB로 약 정수 1,000,000개만 저장할 수 있었다. 100만이 넘는 크기의 int형 배열을 이미 사용하고 있었으므로 이렇게 2차원 배열로 memoization을 이용한 DFS로는 풀 수 없었다. 1차원 배열로 해결하라는 의도 같았다.

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10001];

int coin[101];

int main(void)
{
	int n, k;
	cin >> n >> k;
	
	for(int i=1; i<=n; i++)
		cin >> coin[i];
	
	for(int i= 1; i<=n; i++)
	{
		for(int j= 1; j<=k; j++)
		{
			if(coin[i] <= j)
			{
				if(coin[i] == j)
					dp[j]++;
				else
				{
					dp[j] += dp[j-coin[i]];	
				}
			}
			
		}
	}
	
	cout << dp[k];
}

12865 평범한 배낭 문제를 1차원 배열로 해결하는 방식을 찾아보고 나서 풀이법을 생각해낼 수 있었다.

사실 2차원 배열을 쓰는 것이나 1차원 배열을 쓰는 것이나 불필요한 배열의 사용을 줄일 뿐 풀이 방식은 비슷했다. 이 문제는 아예 1차원 배열만 쓰도록 유도하는 문제 조건이 있어 반복문을 활용하면 반드시 1차원 배열만으로 충분히 풀 수 있을 것이라는 믿음을 갖고 풀었다.

냅색 알고리즘에서 1차원 배열만 쓴다는 것은 n-1 번째 배열로 n번째 배열을 구할 수 있다는 것이고 그렇기에 1차원 배열만으로 충분한 것이라고 추측했다. 앞서 배낭 문제를 해결했던 것처럼 동전의 가치가 담긴 배열을 행으로 삼되 그것을 실제로 배열에 모두 저장하지는 않고 반복문으로 매번 다른 인덱스를 참조하는 용도로만 사용한다. 마치 2차원 배열을 선언하고 반복문으로 한 행 한 행을 탐색하듯이 1차원 배열을 선언하고 매번 다음 동전을 이용해 배열을 반복문의 한 사이클마다 갱신해준다. 이렇게 n번 반복하면 n개의 동전을 모두 사용했을 때의 배열을 구할 수 있다. 이때의 배열은 가치 합이 0부터 k까지 경우의 수를 저장해둔 배열이므로 DP[k]가 정답이 된다.

각 DP[j]는,

• 현재 가치 합(DP 배열의 인덱스에 해당) == coin[i](i번째 동전의 가치) 이라면 +1(자기 자신을 한 번 사용하면 합을 충족시키므로)
• 현재 가치 합보다 동전 가치가 크다면 그대로 유지(이번 동전을 사용할 수 없으므로)
• 현재 가치 합보다 동전 가치가 작다면 +DP[(가치 합 - 동전 가치)]

를 적용하여 반복문 한 사이클마다 DP[K]까지 갱신한다.

DP[(가치 합 - 동전 가치) = (j - coin[i])]은 결국 가치 합이 동전 가치보다 클 때, 해당 가치 합을 채우기 위해선 i번째 동전 가치만큼을 뺀 가치 합을 채우기 위한 경우의 수를 포함한다. 그 경우의 수들에 i번째 동전 가치만큼만, 즉 i번째 동전 하나만 더 보태면 j 를 채우기 때문이다.

예를 들어 동전 2, 3, 5가 있고 3번째 동전인 5로 10을 채우는 상황이라면 3번 동전을 사용가능할 때 5를 만드는 경우의 수는 2 +3 , 5 이렇게 두 가지이고 이들 경우의 수에 +5만 하면 10이 되므로 이 두 경우의 수를 모두 포함하는 것이다. 물론 아예 새로 2를 집어넣는 것이 아니라 이미 있던 값에 2를 더하는 것으로, 동전 2, 3만 있던 2번째 반복문 사이클에서 이미 2+2+2+2+2, 2+2+3+3 이라는 케이스를 카운트 해 둔 상태이다. 이런 방식으로 1차원 배열과 이중 반복문으로 해결할 수 있었다.

n=100이고 k=10000이라면 100 * 10000번 반복하게 되므로 시간 복잡도가 효율적이진 않은 것 같다.

더 간결한 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	vector<int> dp(k+1);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = 1;	// 아무 동전도 선택하지 않은 경우
	for (int i = 0; i < n; i++) { //각 동전에 대해
		for (int j = arr[i]; j <= k; j++) { 
			dp[j] +=dp[j - arr[i]];
		}
	}

	cout<<dp[k]<<endl;
	return 0;
//https://danidani-de.tistory.com/5

내 코드와 풀이 방법은 똑같지만 다른 점은, 우선 가치 합이 0이 되는 경우도 아무것도 고르지 않는 하나의 경우로 간주해 값을 1로 주었다는 것이다. 이 계산을 통해서 따로 if문으로 분기할 필요 없이 점화식 하나로 배열 갱신이 완료된다. 또, 애초에 j의 시작 값을 arr[i]로 주어 어차피 계산이 없을 구간을 건너뛰었다.