백준 1398번: 동전 문제

https://www.acmicpc.net/problem/1398

1398번: 동전 문제

 

k>=0 인 k에 대해서 동전의 종류는 10^k, 25*100^k 로 이루어질 때, 비용을 계산하는 최소한의 동전 갯수를 구하는 문제이다.

 

처음에는 Greedy 방식으로 비용을 비용보다 작은 가장 비싼 동전으로 차감하면서 찾았으나 더 싼 동전으로 더 적은 동전의 갯수만으로 지불할 수 있음을 알게 되었다. 그래서 동전의 종류들을 크기 순서로 나열해 본 결과 동전이 (1 * 10^k, 10 * 10^k, 25 * 10^k ) 구간이 반복됨을 알게 되었고 1~99 구간의 최소 동전의 갯수를 구한 뒤, 비용을 100으로 나누어 가면서 동전의 갯수를 구하면 됨을 알게 되었다. 최소 동전 갯수는 dp로 구하였다.

int[] dp = new int[100];
for (int i = 1; i < 100; i++) {
    dp[i] = i;
    if (i >= 10) {
        dp[i] = Math.min(dp[i], dp[i - 10] + 1);
    }
    if (i >= 25) {
        dp[i] = Math.min(dp[i], dp[i - 25] + 1);
    }
}

 

 

이후, 각각의 비용들을 100으로 나누면서 나머지에 대해 필요한 동전의 갯수를 dp에서 찾아서 누적해준다.

while (t-- > 0) {
    long money = Long.parseLong(br.readLine());
    long totalCoins = 0;
    while (money > 0) {
        int remainder = (int) (money % 100);
        totalCoins += dp[remainder];
        money /= 100;
    }
    sb.append(totalCoins).append('\n');
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 동전문제1398 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] dp = new int[100];
        for (int i = 1; i < 100; i++) {
            dp[i] = i;
            if (i >= 10) {
                dp[i] = Math.min(dp[i], dp[i - 10] + 1);
            }
            if (i >= 25) {
                dp[i] = Math.min(dp[i], dp[i - 25] + 1);
            }
        }
        
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        
        while (t-- > 0) {
            long money = Long.parseLong(br.readLine());
            long totalCoins = 0;
            while (money > 0) {
                int remainder = (int) (money % 100);
                totalCoins += dp[remainder];
                money /= 100;
            }
            sb.append(totalCoins).append('\n');
        }
        br.close();
        System.out.print(sb);
    }
}