풀이 아이디어

다이나믹 프로그래밍

최소 동전 개수로 목표한 금액을 지불하기위해

• 지불할 금액: int n
• 최소 개수로 지불하는 동전 수를 저장하는 배열: int[] dp = new int[n+1];
• 사용가능한 동전 종류를 저장한 배열: int[] coins = new int[]{1,2,5,7};

dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
이 점화식을 사용해서 이전 동전액수에서 다음 액수에 필요한 개수 +1을 해서
dp[n]은 n원을 지불하는 최소 동전 개수를 의미한다.

풀이 코드

import java.io.*;
public class _17212 {
    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[n+1];
        int[] coins = new int[]{1,2,5,7};

        // 최대값으로 초기화
        for(int i=1; i<=n; i++){
            dp[i] = 100000;
        }

        // 최소 개수를 구하기
        for(int i=0;i<4;i++){
            for(int j=coins[i];j<=n;j++){
                dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
            }
        }

        // 결과 출력 
        System.out.println(dp[n]);
    }
}