[백준 - 1398번] 동전 문제 -Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, dp

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.

출력

총 T개의 줄에 각각의 테스트 케이스의 필요한 동전의 개수를 출력한다.

풀이

동전 개수의 최솟값을 구해야 된다.

가치가 큰 동전을 우선적으로 사용하면 최선일까? 아니다.
예를 들어 41같은 경우 25 동전을 사용하면 25 + 10 + 1 6 = 8개지만, 10 4 + 1로 5개가 최솟값이 된다.

가격은 10^15보다 작거나 같은 자연수이기 때문에 모든 가격을 dp로 구할 수는 없다.

잘 보면 규칙성이 보이는데,
k가 0인 경우 1, 10, 25, 100을 사용할 수 있고,

가격의 길이가 짝수인 경우 10, 25을 현재 단위의 맞게 사용하는 것이 최선이 된다.
예를 들면 다음과 같다.

10~99는 10, 25
1000~9999는 1000, 2500

홀수인 경우는 어떨까?

홀수의 경우에는 1를 현재 단위의 맞게 사용하는 것이 최선이다.
예를 들면 다음과 같다.

1~9는 1
100~999는 100

그러면 굳이 모든 가격의 dp를 구하는게 아닌 dp[99]까지만 구하면 모든 가격의 최솟값을 구할 수 있다.

만약 가격이 250111라면, 현재 길이는 짝수다.
그러니까 100000, 250000를 사용하는게 최선이고, dp[99]까지 구해놓았기 때문에 앞 두 자리만 가져온다. 그래서 dp[25]를 더하고, 가격에서 앞 두 자리를 빼주면된다.
111이 된다.

111의 길이는 홀수다.
그러면 100을 사용하는게 최선이고, 앞 한 자리만 가져온다.
dp[1]를 더하고, 가격에서 앞 한 자리만 빼주면 된다.

여기서 앞 두 자리를 가져오지 않는 이유는 홀수일 때 앞 두 자리는 25 단위를 사용하지 않기 때문에 최선이 아니기 때문이다. 그래서 dp[1~9]까지만 사용하는 것이 최선이 된다.

나머지 11은 dp[11]를 더 해주면 최솟값은 4가 된다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int T;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        int[] dp = new int[100]; // 1 ~ 99
        for (int i = 0; i < 100; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[1] = 1;
        dp[10] = 1;
        dp[25] = 1;

        for (int i = 2; i <= 99; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < T; k++) {
            long price = Long.parseLong(br.readLine());
            int answer = 0;
            while (price != 0) {
                int length = String.valueOf(price).length();
                if (length % 2 == 0) {
                    //짝수라면
                    int td = (int) (price / (long) Math.pow(10, length - 2)); //앞 두 자리
                    answer += dp[td];
                    price -= (td * (long) Math.pow(10, length - 2));
                } else {
                    //홀수라면
                    int od = (int) (price / (long) Math.pow(10, length - 1)); //앞 한 자리
                    answer += dp[od];
                    price -= (od * (long) Math.pow(10, length - 1));
                }
            }
            sb.append(answer).append("\n");
        }
        
        System.out.println(sb.toString().trim());
    }
}