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

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

14916번: 거스름돈

✅ 실버 Ⅴ

 

🔶 풀이

편의점 카운터에서 일한다.

2원과 5원만 이용해서 최소한의 동전으로 거스름돈을 주면 된다.

 

해당 문제에 알고리즘 분류는 dp, 그리드 알고리즘

두 가지 방법으로 다 풀어봤다.

 

 

1️⃣ dp

 

Bottom-Up 방법을 사용.

우리가 알 수 있는 작은 문제는 5원까지.

 

1원 = X

2원 = 1개

3원 = X

4원 = 2개

5원 = 1

 

 

6원부터 시작하면 시작하면 된다.

dp[6] = Math.min(dp[6-2], dp[6-5]) → Math.min(dp[4], dp[1]) → 2 와 Integer.MAX_VALUE 중 작은 거에서 동전 하나를 더 쓰므로 +1 해주면 3.

 

dp[7] = Math.min(dp[7-2], dp[7-5]) → Math.min(dp[5], dp[2]) → 1 과 1 중 작은 거에서 동전 하나를 더 쓰므로 +1 해주면 2.

 

·

·

·

 

dp[13] = Math.min(dp[13-2], dp[13-5]) → Math.min(dp[11], dp[8]) → 4 와 4 중 작은 거에서 동전 하나를 더 쓰므로 +1 해주면 5.

 

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));
//      StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(br.readLine());
		
        if (N < 5) {
            System.out.println(N % 2 == 0 ? N/2 : -1);
            return;
        }
		
        int[] dp = new int[N+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
		
        dp[2] = 1;
        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]);
    }
}

 

 

2️⃣ 그리드 알고리즘

 

N이 양수일 때 2원씩 감소시키면서 5원으로 딱 떨어질 때 바로 나누어주면 된다.

반복문이 종료되었을 때 N이 음수가 된다면 불가능한 수라고 판단.

 

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));
//      StringTokenizer st = new StringTokenizer(br.readLine());
		
        int N = Integer.parseInt(br.readLine());
        int ans = 0;
        
        while (N > 0) {
            if (N % 5 == 0) {
                ans = N / 5 + ans;
                break;
            }
            
            N-=2;
            ans++;
        }
        
        if (N < 0) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}