아이디어

• 100 단위마다 끊어서 필요 동전 수를 세자.
  • 100 단위마다 1, 10, 25의 동전이 있는 셈이다.
• 1~100까지의 최소 동전 수는 DP로 구할 수 있다.
  • $f(i) = \min\{(i-1), f(i-10), f(i-25)\} + 1$ ($i < 0$이면 무시)

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();

	static int T, ans;
	static long P;
	
	static int[] memo = new int[100];
	
	public static void main(String[] args) throws Exception {
		memo[0] = 0;
		for (int i=1; i<10; i++)		memo[i] = memo[i-1] + 1;
		for (int i=10; i<25; i++)		memo[i] = min(memo[i-1], memo[i-10]) + 1;
		for (int i=25; i<100; i++)		memo[i] = min(memo[i-1], memo[i-10], memo[i-25]) + 1;
		
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			ans = 0;
			
			P = Long.parseLong(rd.readLine());
			
			for (int i=0; i<8; i++) {
				ans += memo[(int) (P % 100)];
				P /= 100;
			}
			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}
	
	static int min(Integer... A) {
		int min = Integer.MAX_VALUE;
		for (int i=0; i<A.length; i++) {
			min = Math.min(min, A[i]);
		}
		return min;
	}
}

메모리 및 시간

• 메모리: 65832 KB
• 시간: 516 ms

리뷰

• 그리디 단골로 나오는 동전 문제 바리에이션
• 그리디와 DP 풀이 둘 다 알아야 풀 수 있다.
• 골드 2가 골드 4 정도로 내려가도 되지 않을까?