[BOJ/Java] 2839. 설탕 배달

[BOJ/Java] 2839. 설탕 배달

2839번: 설탕 배달

---

풀이

package edu.ssafy.im.BOJ.No2839;

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

public class Main {
    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());

        // dp 알고리즘을 이용하여 최소 개수의 봉지 수 계산
        dp();
    }

    // 동적 계획법을 이용하여 최소 개수의 봉지 수 계산
    private static void dp() {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 2000); // 최대값으로 초기화
        dp[3] = 1; // 초기값 설정
        if (n >= 5)
            dp[5] = 1; // 초기값 설정
        for (int i = 6; i < dp.length; i++) {
            // 현재 무게에서 3kg 봉지를 사용할 경우와 5kg 봉지를 사용할 경우 중 최소값 선택
            dp[i] = Math.min(dp[i - 3] + 1, dp[i - 5] + 1);			
        }
        // 최종 결과 출력
        System.out.println(dp[n] >= 2000 ? -1 : dp[n]);
    }
}