[백준] 17212번 : 달나라 토끼를 위한 구매대금 지불 도우미 – JAVA [자바]

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

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

 

---

• 문제

 

 

---

• 문제 풀이

백준 17212번 달나라 토끼를 위한 구매대금 지불 도우미는 전형적인 1차원 DP 문제이다. 이 문제는 그리고 백준 1463번 1로 만들기와 되게 유사한 문제이다.

 

이 문제에서는 n원이 주어졌을 때 1원, 2원, 5원, 그리고 7원짜리 동전을 가장 적게 써서 n원을 만들어야 한다. 예를 한 번 보겠다.

 

n = 1 : 1원짜리 동전 1개를 써서 만들 수 있다.

 

n = 2 : 2원짜리 동전 1개를 써서 만들 수 있다.

 

n = 3 : 1원짜리 동전 1개와 2원짜리 동전 1개를 써서 만들 수 있다.

 

n = 4 : 2원짜리 동전 2개를 써서 만들 수 있다.

 

n = 5 : 5원짜리 동전 1개를 써서 만들 수 있다.

 

n = 6 : 5원짜리 동전 1개와 1원짜리 동전 1개를 써서 만들 수 있다.

 

n = 7 : 7원짜리 동전 1개를 써서 만들 수 있다.

 

n = 8 : 7원짜리 동전 1개와 1원짜리 동전 1개를 써서 만들 수 있다.

 

 

이렇게 예시에서 볼 수 있듯이 만약에 6원을 만든다고 했을 때 2원짜리 동전 3개를 써서 만들 수 도 있고 1원짜리 동전 6개를 써서 만들 수도 있는데 5원짜리 동전 1개, 그리고 1원짜리 동전 1개를 써야지 최소 개수로 6원을 만들 수 있다.

 

따라서 최소 개수를 구하려면 n원이 주어졌을 때 n-1원이 필요로 했던 동전의 개수, n-2원이 필요로 했던 동전의 개수, n-5원이 필요로 했던 동전의 개수, 그리고 n-7원이 필요로 했던 동전의 개수 중에 최소 개수를 고른 다음 1을 더해주면 된다.

 

dp[n] = Math.min(dp[n-1], Math.min(dp[n-2], Math.min(dp[n-5], dp[n-7]) + 1;

 

---

• 코드

 

import java.io.*;
import java.util.*;
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[100001];
        dp[1] = 1;
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 2;
        dp[5] = 1;
        dp[6] = 2;
        dp[7] = 1;
        for (int i = 8; i <= n; i++) {
            dp[i] = Math.min(dp[i-1], Math.min(dp[i-2], Math.min(dp[i-5], dp[i-7]))) +1;
        }
        System.out.print(dp[n]);
    }
}

 

---

• 후기

나는 이전에 이 문제와 매우 유사한 문제를 풀어본 적이 있어서 쉽게 접근할 수 있었다. 이런 유형의 문제를 처음 풀어보는 거면 이 문제를 꼭 이해하는 게 중요할 거 같다.