백준 14916: 거스름돈 [JAVA]

[문제 링크]

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

[난이도]

- Silver 5

 

[알고리즘]

- DP

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int INF = Integer.MAX_VALUE;
    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[0] = INF;
        dp[1] = INF;
        dp[2] = 1;
        dp[3] = INF;
        dp[4] = 2;
        dp[5] = 1;

        for (int i = 6; i <= n; i++) {
            dp[i] = Math.min(dp[i - 2], dp[i - 5]) + 1;
        }
        System.out.println(dp[n] == INF ? -1 : dp[n]);
    }
}

[풀이]

DP로 문제를 풀어보았다. Bottom-up방식으로 풀었다.

1. 문제를 하위문제로 쪼갠다

dp[1] = 동전을 못거슬러줌
dp[2] = 2원짜리 하나 거슬러줌
dp[3] = 2원짜리 하나 거슬러줘도, 남은1원을 못거슬러줌
dp[4] = 2원짜리로 2개
dp[5] = 5원짜리 하나 
dp[6] = 5원짜리 하나, 남은 1원못거슬러줌 
            2원짜리 3개거슬러줌

 

2. 관계를 수식화
5원을 거슬러줄때랑 2원을 거슬러줄때랑을 둘 다 고려해야함

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

 

3. 초기값 설정

dp[0] = INF

dp[1] = INF

dp[2] = 1

dp[3] = INF

dp[4] = 2

dp[5] = 1

 

[출처]

https://tang25.tistory.com/entry/%EC%9E%90%EB%B0%94%EB%B0%B1%EC%A4%80-9625%EB%B2%88-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EC%97%84%ED%83%B1