[백준] 2839번: 설탕 배달 (Java)

1. 문제설명

상근이는 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕을 담는 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 최대한 적은 봉지를 들고 가려고 한다.

• 시간 제한: 1초
• 메모리 제한: 128MB

 

2. 접근 방식

• `dp[i]`를 설탕 무게가 `i`일 때 필요한 최소 봉지 개수를 저장한다.
• `dp[1] ~ dp[5]` 에 초기값을 설정한다.
• `i=6` 부터는 `dp[i-3]`과 `dp[i-5]`의 값을 고려하여 계산한다.
  • 한 쪽만 0이 아닌 경우: 0이 아닌 값 + 1
  • 두 쪽 모두 0이 아닌 경우: `Math.min(dp[i-3], dp[i-5]) + 1`
  • 모두 0인 경우: 0으로 설정
• 최종적으로 `dp[n]`이 0이면 -1을 출력, 아니면 dp[n]값을 출력한다.

 

3. 최종 코드

import java.io.*;

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[5001]; // 최소 봉지 개수 저장
        dp[1] = 0; dp[2] = 0; dp[4] = 0; // 1,2,4는 0으로 초기화
        dp[3] = 1; dp[5] = 1; // 3,5는 1로 초기화

        // 6부터 n까지 dp값 계산
        for(int i=6; i<=n; i++) {
            // 3kg 봉지로 만들 수 없고 5kg 봉지로 만들 수 있는 경우
            if(dp[i-3]==0 && dp[i-5]!=0)
                dp[i] = dp[i-5] + 1;
            // 3kg 봉지로 만들 수 있고 5kg 봉지로 만들 수 없는 경우
            else if(dp[i-3]!=0 && dp[i-5]==0)
                dp[i] = dp[i-3] + 1;
            // 3kg과 5kg 봉지 모두 사용 가능한 경우
            else if(dp[i-3]!=0 && dp[i-5]!=0)
                // 최소 개수를 선택
                dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
            // 어떤 경우에도 만들 수 없는 경우
            else dp[i] = 0;
        }

        // n에 해당하는 dp 값이 0이라면 -1 출력 (불가능)
        if(dp[n] == 0) System.out.println(-1);
        else System.out.println(dp[n]);
    }
}