[ boj : 2091] 동전

www.acmicpc.net/problem/2091

2091번: 동전

문제 : 1,5,10,25 센트가 각각 존재합니다. 이때 x를 만들수 있는 경우의 수 중 가장 많은 동전을 사용했을때 각각의 센트수를 출력하시면 됩니다.

 

해설: 이 문제 현재 골4로 측정되어있는데 절대 아닌 것 같아요,,,,,(갓님들 티어조정좀 ㅠㅠㅠ)

일단 다양한 방법이 존재하는 것 같습니다.(그리디,다이나믹 프로그래밍,브루트 포스)

 

그러나 전 dp 와 dp+브루트포스 로 풀었는데 그냥 dp 로 푼 걸로 설명하겠습니다.(브루트 포스 궁금하시면 댓글로 남겨주세요)

 

점화식을 어떻게 세워야 되는지 생각해 보면 각 동전의 금액과 개수가 주어져 있고 x라는 목표가 있으니 이걸 어떻게 활용해 봅시다.

 

dp[i][j] = i 원일때 최대의 동전수를 사용했다고 가정하면, 이때 j 동전의 개수

라고 잡았습니다.

 

그럼 총 dp 테이블은 dp[1~x][0~5] 까지 되겠죠.( 0 : 1cent 개수, 1 : 5cent 개수, 2 : 10cent 개수 , 3 : 25cent 개수 , 4 : 총동전의 개수)

 

만약 현재 1cent를 사용해서 k 원을 만들려고 하면 k-1 원을 확인하면 되겠죠. 이때, k-1원을 만든 동전의 개수들이 현재 k 원을 만들었을때 동전의 수보다 많다면 갱신 해주고 1cent의 개수를 하나 줄여줍니다. 만약 1cent를 더이상 사용할 수 없으면 그냥 넘어갑니다.

이런식으로 한줄 씩 갱신해 나아가면됩니다. 주의할 점은 dp 테이블을 0으로 초기화 시키면 안됩니다. 이유는 동전을 사용하지 않았을 경우 0 이니 겹치게 되 잘못된 값을 도출시킵니다.

 

#include<bits/stdc++.h>

using namespace std;

int num[] = { 1,5,10,25 };
int x,coin[4], dp[10001][5];

int main()
{
	cin >> x;
	for (int i = 0; i < 4; i++)cin >> coin[i];

	memset(dp, -1, sizeof(dp));

	for (int i = 0; i <= 4; i++)dp[0][i] = 0;

	for (int i = 1; i <= x; i++) {
		for (int j = 0; j < 4; j++) {
			if(dp[i][j]==-1)dp[i][j] = 0;
			if (i - num[j] < 0)continue;
			if (dp[i - num[j]][4] > dp[i][4]) {				
				if (coin[j] >= (dp[i - num[j]][j] + 1)) {
					for (int k = 0; k < 4; k++)
						dp[i][k] = dp[i - num[j]][k];
					dp[i][4] = dp[i - num[j]][4] + 1;
					dp[i][j] += 1;
				}
			}
		}
	}
	for (int i = 0; i < 4; i++)cout << dp[x][i] << " ";
	return 0;
}