[자바] 백준 17212 - 달나라 토끼를 위한 구매대금 지불 도우미 (boj java)

문제 : boj17212

 

  N을 1,2,5,7원들을 최소한으로 사용한 합으로 나타내야 하는 문제이다. dp로 쉽게 풀 수 있다. 점화식은 다음과 같다.

  dp[i]는 i원을 표현하기 위해 필요한 1,2,5,7원 동전의 최소 개수이다. dp[0] = 0을 base condition으로 둔다면 위의 점화식을 통해 N이하의 모든 값에 대해 최소 개수를 구할 수 있다. 답은 dp[n]이 될 것이다. 말로 표현하자면 "i원(dp[i])을 표현하기 위한 최소개수는 i-1원의 최소개수, i-2원의 최소개수, i-5원의 최소개수, i-7원의 최소개수 중 가장 작은 회수에다가 현재의 동전 1개를 추가한(+1) 개수이다."

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static final int[] coin = {1,2,5,7};
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[n+1];
        Arrays.fill(dp, 100001);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 4; j++) {
                if (i-coin[j]<0) continue;
                dp[i] = Math.min(dp[i], dp[i-coin[j]]+1);
            }
        }
        System.out.print(dp[n]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}