[백준] 2839 설탕 배달 (java)

 

2839번: 설탕 배달

해설

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력해야한다.

초기값으로 dp[3]과 dp[5]를 1로 하고, dp[n-3]+1과 dp[n-5]+1의 최솟값을 잡는 dp로 풀었다. 만약 20000보다 큰게 나오면 딱 맞게 담을 수 없다는 의미이므로 -1을 반환한다.

 

풀이

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

// 설탕 배달 : dp
public class Question3 {
    static int n;
    static int ans = Integer.MAX_VALUE;

	public static void main(String[] args) throws NumberFormatException, IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	    n = Integer.parseInt(br.readLine());
	//        greedy(n);
	
	//        recursive(n, 0);
	//        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
	
	    dp();
	}
	
	// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	// x x 1 x 1 2 x 2 3 2 3 4 3 4 3
	// Math.min(dp[n-3] + 1, dp[n-5] + 1)
	// 각 무게 당 필요한 봉지 수를 저장할 배열을 선언합니다
	private static void dp() {
	    int[] dp = new int[n + 1];
	    Arrays.fill(dp, 20000);
	    dp[3] = 1;
	    if (n >= 5) {
	        dp[5] = 1;
	    	for (int i = 6; i <= n; i++) {
	    		dp[i] = Math.min(dp[i - 3] + 1, dp[i - 5] + 1);            
	    	}
	    }
    	System.out.println(dp[n] >= 20000 ? -1 : dp[n]);
	}
	
	private static void recursive(int n, int cnt) {
	    // basis part
	    if (n < 0) {
	        return;
	    }
	    if (n == 0) {
	        ans = Math.min(ans, cnt);
	        return;
	    }
	
	    // inductive part
	    recursive(n - 5, cnt + 1);
	    recursive(n - 3, cnt + 1);
	}
	//    private static void greedy(int n) {
	//        int cnt = 0;
	//
	//        while(n%5 != 0) {
	//            n -= 3;
	//            cnt++;
	//        }
	//        if(n<0) {
	//            System.out.println(-1);
	//        } else {
	//            cnt += n/5;
	//            System.out.println(cnt);
	//        }
	//    }
}