[백준] 14916 거스름돈 - DP JAVA

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

14916번: 거스름돈

코드설명

DP 문제입니다.

각 액수를 만들기 위한 DP를 만들고,  해당 값에 2원과 5원을 더하는 경우의 최소값을 구한뒤 추가로 2원과 5원을 더하는경우로 1을 더해가며 진행했습니다.

 

DP로 풀지않고 반복문을 활용하여 해결도 가능합니다.

N에 만약 5로 나눠진다면 5로 나눈값을 더해주고 반복문을 끝냅니다.

만약 5로 나누어지지않는다면, -2 를 계속해서 진행해줍니다.

위의 과정을 N이 > 0 인 동안 계속해서 진행하면됩니다.

마지막에 N == 0 이 아니라면, (N < 0 이라면) 해당 계산은 불가능한것이므로, -1 을 출력합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	dp = new int[100001];
    	dp[0] = 0;
    	dp[1] = 0;
    	dp[2] = 1;
    	dp[3] = 0;
    	dp[4] = 2;
    	dp[5] = 1;
    	
    	for(int i=6; i<=N;i++) {
    		if(dp[i-2] == 0 && dp[i-5] == 0 ) {
    			dp[i] = 0;
    		}
    		else if(dp[i-2] > 0 && dp[i-5] == 0 ) {
    			dp[i] = dp[i-2] + 1;
    		}
    		else if(dp[i-2] == 0 && dp[i-5] > 0 ) {
    			dp[i] = dp[i-5] + 1;
    		}else {
    			dp[i] = Math.min(dp[i-2], dp[i-5]) + 1;
    		}
    	}
    	
    	if(dp[N] == 0)
    		System.out.println("-1");
    	else
    		System.out.println(dp[N]);
    	
    }
}