[백준 1398] 동전 문제 (JAVA)

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

1398번: 동전 문제

 

1         10           25 

100     1000       2500

10000 1000000 250000

 

이렇게 100을 곱한 값으로 나눌 수 있다.

사이즈가 100인 dp 배열을 만들어, 해당 인덱스의 값일 경우 지불해야 하는 동전의 개수를 세팅해놓는다.

dp[input 값에 %100한 값] 을 모두 더하면 필요한 동전의 개수가 나온다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp= new int[100];
		for(int i=0;i<100;i++) {
			if(i>=25) {
				dp[i]=Math.min(dp[i-25]+1, dp[i-10]+1);
				dp[i]=Math.min(dp[i],dp[i-1]+1);
			}else if(i>=10) {
				dp[i]=Math.min(dp[i-10]+1, dp[i-1]+1);
			}else {
				dp[i]=i;
			}
		}
		
		for (int i = 0; i < n; i++) {
			Long num = Long.parseLong(br.readLine());
			//1   100
			//10  1000
			//25  2500
			int result=0;
			while(num>0) {
				result+=dp[(int) (num%100)];
				num/=100;
			}
			System.out.println(result);
		}
	}

}