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

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

사실 DP 문제는 점화식만 잘 짜면 그 뒤로는 쉽다. 그래서 나는 DP 문제를 마주하면 먼저 나 혼자 계산해 본다.

 

n = x 일 때 => 봉지 개수

n = 3 ⇒ 1

n = 4 ⇒ -1;

n = 5 ⇒ 1

n = 6 ⇒ 2

n = 7 ⇒ -1;

n = 8 ⇒ 2

n = 9 ⇒ 3

n = 10 ⇒ 2

n = 11 ⇒ 3

n = 12 ⇒ 4

n = 13 ⇒ 3

n = 14 ⇒ 4

n = 15 ⇒ 3

n = 16 ⇒ 4

n = 17 ⇒ 5

n = 18 ⇒ 4

n = 19 ⇒ 5

n = 20 ⇒ 4

n = 21 ⇒ 5

...

...

 

 

먼저 보면 n 에서는 3과 5만 더할 수 있다. 그 말은 즉, dp[n] 은 n - 5 혹은 n - 3 에서 하나를 더한 값이 된다는 것이다. 

 

보면 알 것이다. 10 킬로그램(n = 10)을 배달해야 한다고 가정해 보자. 위에 나와있듯이 10의 최소는 2개(5, 5) 이다. n - 5 에서 하나를 더한 값이다. 모든 n이 그렇다. 

 

 

그럼 이제 우리는 패턴을 파악한 것이다. 

 

점화식: dp[i] = dp[i - 5] + 1 혹은 dp[i] = dp [i - 3] + 1 이다.

 

 

하지만 예외처리를 해주어야 한다. 

 

정확하게 N 킬로그램으로 만들지 못한다면 -1 을 출력해야 한다. 

 

 

 

  풀이

 

설계 내용

 

package src.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Sugar_Delivery {
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] dp = new int[n + 1];

        for(int i = 3; i <= n; i++){
            if(i == 3 || i == 5) {
                dp[i] = 1;
                continue;
            } else if(i == 4 || i == 7){
                dp[i] = -1;
                continue;
            }
            if(dp[i - 5] > 0){
                dp[i] = dp[i - 5] + 1;
            } else if(dp[i - 3] > 0){
                dp[i] = dp[i - 3] + 1;
            }
        }

        System.out.println(dp[n]);

    }
}