거스름돈 - 14916

문제

풀이

import java.util.Scanner;

// 거스름돈 - s5 - DP
public class ex14916 {

    static int n;
    static long[] dp = new long[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        dp[0]=-1;
        dp[1]=-1;
        dp[2]=1;
        dp[3]=-1;
        dp[4]=2;
        dp[5]=1;
        dp[6]=3;
        dp[7]=2;
        dp[8]=4;
        dp[9]=3;
        dp[10]=2;

        for(int i=11; i<=n; i++){
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i=11; 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.println(dp[n]);
    }
}

우선 문제를 봤을 때 당연히 DFS가 생각난다. 하지만 제한사항 보면 n값이 너무 크기 때문에 자동으로 DP알고리즘으로 분류된다. 하지만 이 문제는 간단해서 그냥 풀 수도 있다. 그래도 DP를 공부하기 위해서 DP방식으로 진행했다.

1. 테이블 정의
2. 규칙찾아서 점화식 구현
3. 출력

우선 10원까지의 거스름돈 동전 수를 직접 입력했다. 그 후에 규칙을 찾았다. 2,5원으로 구성되기 때문에 dp[i-2]인 경우와 dp[i-5]인 경우에서 +1을 해주면 된다. 하지만 거슬러 주지 못하는 경우 -1을 출력해주어야한다. 또한 2원으로는 안되고 5원으로는 되고 , 그 반대인 경우를 체크해줘야한다.

1. 2원과 5원으로 거슬러주지 못하는 경우
2. 2원으로 거슬러 주지 못하는 경우
3. 5원으로 거슬러 주지 못하는 경우
4. 점화식 : dp[i] = Math.min(dp[i-2],dp[i-5])+1;