[백준] 14916번 : 거스름돈 – JAVA [자바]

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

14916번: 거스름돈

 

---

• 문제

 

 

---

• 문제 풀이

백준 14916번 거스름돈은 1로 만들기와 비슷한 DP 문제이다. 이 문제에서는 입력으로 돈 n원이 주어지고 2원짜리 동전과 5원짜리 동전으로 최소의 동전을 써서 거스름돈을 주어야 한다. 그리고 이 돈 n원을 거슬러 줄 수 없으면 -1을 출력하면 된다.

 

우선 n원을 거슬러 줄 수 없다는 것은 2원과 5원짜리 동전으로 만들 수 없는 돈을 뜻한다. 1 원하고 3원만 거슬러 줄 수 없다. 나머지 돈들은 2 원하고 5원을 조합하면 만들 수 있다.

 

우선 int형 배열 dp를 만들고 dp [1]부터 dp [5] 까지를 다음과 같이 초기화한다.

dp [1] = -1;

dp [2] = 1;

dp [3] = -1;

dp [4] = 2;

dp [5] = 1;

 

그리고 인덱스 6부터 n까지는 INTEGER.MAX_VALUE로 초기화한다. 초기화하면 다음과 같다.

 

그리고 for-loop을 6부터 n까지 돌린다. 세 가지의 경우가 나온다.

 

1) 만약에 dp [i-2] = -1이면 dp [i-5] + 1을 dp [i]에 저장한다.

 

2) 만약에 dp [i-5] = -1이면 dp [i-2] + 1을 dp [i]에 저장한다.

 

3) dp [i] = Math.min (dp [i-2], dp [i-5]) + 1

 

인덱스 10까지 하면 다음과 같은 dp 테이블을 구할 수 있다.

 

---

• 코드

 

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] = -1;
        dp[4] = 2;
        dp[5] = 1;
        for (int i = 6; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 6; i <= n; i++) {
            if (dp[i-2] == -1 && dp[i-5] == -1) {
                dp[i] = -1;
            } else if (dp[i-2] == -1) {
                dp[i] = dp[i-5] + 1;
            } else if (dp[i-5] == -1) {
                dp[i] = dp[i-2] + 1;
            } else {
                dp[i] = Math.min(dp[i-2], dp[i-5]) + 1;
            }
        }
        System.out.print(dp[n]);
    }
}

 

---

• 후기

이런 문제의 유형이 되게 많기 때문에 이해만 하면 이런 유형들은 쉽게 풀 수 있다.