[백준/C++] 2294 동전2 (G5)

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

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int dp[10001] = {};
    int coin[101]={};
    
    int n , k;
    cin >> n >> k;
    
    for(int i= 1; i <=n; i++)
    {
        cin >> coin[i];
    }
    sort(coin, coin+n+1);
    
    for(int i = 0; i<= k; i++)
        dp[i] = 10001;
    
    for(int i = 1; i<= n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            if(j%coin[i]==0)
                dp[j] = j/coin[i];
            else if(dp[j-coin[i]]!=-1)
                dp[j] = min(dp[j-coin[i]]+1, dp[j]);
        }
    }
    
    //for(int i=0;i<=k;i++)
    //    cout<<dp[i]<<" ";
    
    if(dp[k]==10001)
        cout<<-1;
    else
        cout << dp[k];
}

  앞서 풀었던 동전 1 문제와 마찬가지로 맞춰야 하는 가치 합을 인덱스로 갖는 1차원 배열 dp를 이용했다. 배열에는 해당 합을 만들 수 있는 최소 동전의 개수를 저장했다. 동전을 오름차순으로 정렬하고 1개일 때, 2개일 때, … , n개일 때까지 진행하며 배열을 갱신한다.

  예를 들어 가치 2인 동전일 때 가치 합 j 를 채우는 최소 경우의 수를 적어가며 배열을 갱신하는 것인데, 이 때 동전 가치의 배열이 오름차순 정렬되어 있으므로 가치 합과 동전이 나눠 떨어진다면 그 몫을 바로 넣어주고(무조건 최소 개수이므로) 그렇지 않다면 이미 적혀있는 값(이전 동전까지를 사용해서 j를 만들 수 있는 최소 동전 개수)과 무게 j 에서 지금 동전 가치만큼을 뺀 무게의 최소 동전 갯수 +1 값을 비교하여 더 작은 것으로 배열을 채운다.

동전 가치가 1, 5, 12 일 때 k = 15을 채우기 위해서 1, 5까지 사용했을 때는 5+ 5+ 5로 3개 , 12까지 사용할 수 있을 땐 12 + 1 + 1 + 1(dp[3] = 3에 12를 추가로 사용 → +1 = 4개) 두 가지 경우를 비교할 수 있는 것이다. 이런 식으로 배열을 계속 갱신해나가면 dp[k]에는 최소 사용 횟수가 저장된다.

  이런 문제를 풀 때 계속 이전 경우를 어떻게 다 고려할지 고민하게 된다. 자연스럽게 한 경우를 따지고 그 다음 경우를 따질 때 비교와 최적 해의 저장을 통해 누적으로 앞선 모든 경우가 고려되게끔 코드를 짜야하는 것 같다.

더 간결한 코드

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

int dp[10001] = { 0, };
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n,k;
	cin >> n>>k; //n개의 동전, k원을 만들어야 한다.
	vector<int>money(n+1);
	for (int i = 1; i <= n; i++) cin >> money[i];

	//문제 해결
	for (int i = 1; i <= k; i++) dp[i] = 10001; //최솟값을 구하기 위함

	for (int i = 1; i <= n; i++) { // money[i] 동전을 가지고
		for (int j = money[i]; j <= k; j++) { // 최솟값을 만들 수 있으면 갱신
			dp[j] = min(dp[j], dp[j - money[i]] + 1);
		}
	}

	//결과 출력
	if (dp[k] == 10001) cout << -1 << '\\n';
	else cout << dp[k] << '\\n';
}
//https://gyong0117.tistory.com/entry/BOJ%EB%B0%B1%EC%A4%80-2294C-%EB%8F%99%EC%A0%84-2

  내 코드와 차이점은 dp[0]= 0 이라는 점이다. 이 점 덕분에 나누어 떨어질 때를 특정하여 해당 몫으로 배열을 채워넣는 if문을 생략하고 dp[j] = min(dp[j], dp[j - money[i]] + 1) 점화식만으로 모든 배열을 채울 수 있다.