[백준 BOJ] 14916번 거스름돈 (자바/DP)

문제

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

 

접근 방법

1. DP 문제

 

2. 점화식 : dp[i] = Math.min(dp[i-2], dp[i-5) + 1

 

3. 초기화

dp[2] = 1(2원 짜리 하나를 사용하여 거슬러 줄 수 있으므로)

dp[5] = 1(5원 짜리 하나를 사용하여 거슬러 줄 수 있으므로)

dp[4] = 2(2원 짜리 2개로 거슬러 줄 수 있으므로)

 

/*
 * boj 14916 거스름돈
 * dp 문제
 * */
public class Main_14916 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int[] dp = new int[n+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		dp[2] = dp[5] = 1; dp[4] = 2;
		
		
		//n원을 거슬러줄 때 최적
		for (int i = 6; i < dp.length; i++) {
			dp[i] = Math.min(dp[i-2], dp[i-5]) + 1;
		}
		
		int result = dp[n];
		
		System.out.println(result == Integer.MAX_VALUE ? -1 : result);
	}
}