[Java] 백준 2839. 설탕 배달

문제

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

2839번: 설탕 배달

알아야 할 개념

• 다이나믹 프로그래밍

풀이

풀이는 다음과 같다. 

1. dp 배열을 하나 만들고 최대 값 10001로 채운다. 
2. dp 배열에 (idx == 3의 배수)를 3으로 나눈 몫으로 채운다. 
3. dp 배열을 순회 하면서, dp[i-5] (이전에 최소값 봉지의 개수) + 1 , dp[i] (현재 개수 ) 두 값의 최솟값으로 업데이트한다.
4. dp[ 주어진 숫자 ] 를 리턴한다. 

참고

dp[i-5] + 1 을 한 이유는 대부분의 다이나믹 프로그래밍 풀이가 그러듯이 이전에 구했던 최소 개수를 가져온다는 뜻이다. 

dp[i-5] == 이전에 구한 봉지의 개수 최솟값에  + 1 == 이번에 봉지 하나를 추가하니깐 1을 더한다. 

 

코드

자바

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

class Main{
    public static void main(String[] args)throws IOException{
        Main s = new Main();
        s.sol();
    }
    public void sol() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int dp[] = new int[n+1];
        int max = 10001;
        Arrays.fill(dp,max);
        dp[3] = 1;
        
        
        for(int i = 6; i < n+1; i+=3){
            dp[i] = dp[i-3]+1;
        }
        
        for(int i = 5; i <n+1; i++){
            if(i == 5){
                dp[i] = 1;
            }else{
                dp[i] = Math.min(dp[i], dp[i-5]+1);
            }
        }
        System.out.println(dp[n] >= max ? -1 : dp[n]);
    }
}