[BOJ_17212] 달나라 토끼를 위한 구매대금 지불 도우미

설명

---

dp의 인덱스가 money 만큼 빠지는 것으로 생각하고 풀면 쉽게 접근이 가능한 문제이나 이를 깨닫지 못한다면 풀기가 많ㅇ이 함들다.

 

코드

---

package BOJ.Dynamic_Programming;

import java.util.Scanner;
public class BOJ_17212 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] coins = {1, 2, 5, 7};
        int[] dp = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for (int i = 1; i <= N; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        System.out.println(dp[N]);
        sc.close();
    }
}

 

17212번: 달나라 토끼를 위한 구매대금 지불 도우미