[백준] 14916번 거스름돈 JAVA (자바) 풀이

문제 14916번 (DP)

 :  거스름돈 = 2원, 5원

 

 :  거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램

 

 :  예) 거스름돈이 15원이면 5원짜리 3개, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개

 

 

 

[입력]

 :  첫째 줄에 거스름돈 액수 n (1 ≤ n ≤ 100,000)

 

 

[출력]

 :  거스름돈 동전의 최소 개수를 출력 (거슬러 줄 수 없으면 -1 출력)

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. 탑다운 vs 바텀업

 

거스름돈이 작은 것부터 해결해서 점차 빌드업한다

모두 계산해야 답이 나온다

 

    → 바텀업으로 풀기

 

2.식세우기

 

dp[n] = dp[n-2] / dp[n] = dp[n-5] 활용

 

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

    → 마지막에 1을 더한 이유는 count 같은 개념이다

 

3.기타

 

n입력이 1부터 들어오기 때문에 dp는 0이 아닌 1부터 시작해도 괜찮다

 

 

 

 [코드]

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];
        int INF = Integer.MAX_VALUE;
        
        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]);
    }
}

 

 

 [해설]
     

 :  int n = Integer.parseInt(br.readLine());  입력
    int dp[]= new int[100001];  dp 크키 그냥 n+1로 하면 바로 런타임 에러
    int INF = Integer.MAX_VALUE;  최대값으로 해야 min값 구할 수 있따
        
 :  dp[1] = INF; 
    dp[2] = 1;
    dp[3] = INF;
    dp[4] = 2;
    dp[5] = 1;
        
 :  for(int i=6; i<=n; i++){  6부터 dp 시작
            dp[i] = Math.min(dp[i-2], dp[i-5])+1; 최소값 구하고 바로 1 count
    }
        
 :  System.out.println(dp[n]==INF?-1:dp[n]);  INF면 -1로 출력하고 아니면 dp[n] 바로 출력

 

 

 

 

이제 풀어보러 갈께요 :)

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *