문제 링크
문제
티어: 골드3
알고리즘: 다이나믹 프로그래밍
찰리는 돈을 좀 가지고 있다. 그는 특히 동전에 관심이 좀 있어서 동전을 여러 개 가지고 있다. 그런데 동전이 자꾸 쌓여가자, 그는 처리에 곤란을 느끼고 이 동전들을 처분하기로 마음먹었다.
찰리는 1센트(cent)짜리 동전을 A개, 5센트(nickel)짜리 동전을 B개, 10센트(dime)짜리 동전을 C개, 25센트(quarter)짜리 동전을 D개 가지고 있다. 찰리는 이를 이용하여 X원짜리 커피를 사려 하는데, 이때 사용하는 동전의 개수를 최대로 하려 한다.
이러한 정보가 주어질 때, 사용하는 동전의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 다섯 정수 X, A, B, C, D가 주어진다.
출력
첫째 줄에 답을 출력한다. cent의 수, nickel의 수, dime의 수, quarter의 수를 출력한다. 불가능한 경우에는 0을 네 개 출력한다.
제한
- 1 ≤ X ≤ 10,000
- 0 ≤ A, B, C, D ≤ 10,000
풀이
구하고자 하는 것은 X원 짜리 커피를 살 때 최대한 많은 동전을 사용해 그 개수를 구하는 것이다.
최대한 많은 동전을 사용하려면 당연히 가치가 작은 동전을 우선적으로 사용해야 한다.
예를 들어 15원을 채울 때 5원으로 3개를 채울 수 있지만 1원으로는 15개를 채울 수 있다.
그래서 처음에 나는 1원부터 최대한 채웠다. 이때 1원으로 다 채울 수 없다면 다음으로 가치가 큰 5원을 이용해서 X원을 만들어줘야 하기 때문에 1원을 최대한 쓰면서 남은 값이 5의 배수가 되게끔 해줬다. 그리고 5원으로 다 채울 수 없다면 같은 방법으로 10원 다음은 25원 반복해 줬고,
1 -> 5 -> 10 -> 25 순으로 X원을 만들어주지 못했다면 다음과 같은 순으로 다시 반복해 줬다.
1 -> 5 -> 25
1 -> 10 -> 25
1 -> 25
이 방식은 큰 헛점이 있었다. 가치가 적은 동전 개수를 최대로 한다고 해서 결괏값이 최대가 되진 않는다.
예를 들어
X가 50이고, A -> 0, B -> 1, 10 -> 5, 25 -> 2 일 때
5원 한개 사용되면 45원이다.
이때 10원으로 50원을 채워줄 수 없기 때문에
10원은 2개만 사용되어야 하고,
결과적으로 0, 1, 2, 1이 사용된다.
만약 5원을 0개 사용했다면
10원으로 50원을 채워줄 수 있기 때문에
결과적으로 0, 0, 5, 0으로 더 많은 동전을 사용한 것을 알 수 있다.
그러면 결국 브루트 포스로 전체 경우의 수를 따져봐야 하는데 처음에 당연히 불가능 하다고 생각했다. 하지만 제한을 보니 충분히 가능한 경우의 수라는 것을 나중에 알 수 있었다.
다음 생각한 알고리즘은 다이나믹 프로그래밍이다.
1부터 X원까지 차례대로 최대 동전의 개수를 구하는 것이다. 이때 전에 저장된 값을 이용한다.
생각해 보면 이미 전에 구해놨던 동전의 개수를 이용한다면 보정해 줄 필요 없이 간단하게 최대 동전의 개수를 구할 수 있다.
예를 들어
X = 11이고, A -> 10, B -> 1, C -> 1, D -> 0개면
dp[1] -> A 1개
dp[2] -> A 2개
dp[3] -> A 3개
dp[4] -> A 4개
dp[5] -> A 5개
dp[6] -> A 6개
dp[7] -> A 7개
dp[8] -> A 8개
dp[9] -> A 9개
dp[10] -> A 10개
(당연히 index 10까지 전에 값을 이용해 구한 값이다.)
이때 11이 문제인데 전에 풀이였다면, 이를 보정하기 위해서 A의 동전을 빼가며 B의 배수에 맞추는 과정을 거쳐야 했다.
하지만 dp풀이는 그런 보정이 필요 없다. 그냥 4가지 경우만 따지면 된다.
동전은 1, 5, 10, 15가 있기 때문에
dp[11 - 1] + 1원 동전 추가 -> 불가능 1원 개수 부족
dp[11 - 5] + 5원 동전 추가 -> 가능
dp[11 - 10] + 10원 동전 추가 -> 가능
dp[11 - 25] + 25원 동전 추가 -> 불가능
5센트랑 10센트를 추가하는 것이 가능하다.
우리가 구하고자 하는 것은 최대 동전의 개수이기 때문에
최종답은 dp[6] + 5원 동전 추가다.
그래서 6 1 0 0이 답이 된다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int X, A, B, C, D;
static int dp[][];
static final int[] coinCnt = new int[4];
static final int[] cw = {1, 5, 10, 25}; //가중치
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
X = Integer.parseInt(st.nextToken());
for(int i=0; i<4; i++) {
coinCnt[i] = Integer.parseInt(st.nextToken());
}
dp = new int[X + 1][5]; //0 -> A, 1 -> B, 2 -> C, 3 -> D, 4 -> 총 개수;
for(int i=1; i<=X; i++) {
dp[i][4] = -1;
}
for(int i=1; i<=X; i++) {
dp[i][4] = 0;
for(int j=0; j<4; j++) {
if(i - cw[j] < 0 || dp[i - cw[j]][4] == -1) {
continue;
}
if(dp[i - cw[j]][j] + 1 <= coinCnt[j]) {
//coin을 추가해도 정해진 개수를 초과하지 않는다면
if(dp[i - cw[j]][4] + 1 > dp[i][4]) {
//현재 코인 총 개수보다 크다면 업데이트
dpUpdate(j, dp[i - cw[j]], i);
}
}
}
if(dp[i][4] == 0) {
//update 안됨 만족하는 값이 없는거임
dp[i][4] = -1;
}
}
StringBuilder sb = new StringBuilder();
for(int i=0; i<4; i++) {
sb.append(dp[X][i]).append(" ");
}
System.out.println(sb.toString().trim());
}
static void dpUpdate(int coinInd, int[] beforeDp, int updateInd) {
int cnt = 0;
for(int i=0; i<4; i++) {
if(i == coinInd) {
dp[updateInd][i] = beforeDp[i] + 1;
} else {
dp[updateInd][i] = beforeDp[i];
}
cnt += dp[updateInd][i];
}
dp[updateInd][4] = cnt;
}
}