[백준] 2839번 설탕 배달 DP 문제 풀이

 

2839번
/
설탕 배달
https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

---

 

문제

 

 

접근

그리디 알고리즘이면서 DP로도 해결 가능한 문제이다.

이번 시간에는 DP로 풀어보겠다.

 

여느 DP 문제가 그렇듯 DP 배열 안에 담을 수 있게끔 일정한 규칙을 찾는게 키 포인트다.

각자 방식은 다를 수 있으나, 나같은 경우는 일단 케이스를 여러개 만들어서 그 안에서 규칙을 찾았다.

 

배달해야하는 각 무게마다 설탕 봉지의 최소 개수를 세어보면 위와 같다.

 

8Kg부터는 어떻게 조합을 해도 3Kg과 5Kg의 봉지로 무조건 맞아 떨어지는 것을 알 수 있다.

 

또한, 5Kg 이후부터 각 무게에서의 개수를 보자.

 

현재 무게에서 -3, -5 위치에 있는 값 중 더 작은 값에 +1을 한 게 현재 무게 위치의 값이 되는 것을 찾을 수 있다.

 

dp[3]과 dp[5]를 1로 초기값을 잡아주고, -1이 되는 위치들만 처리하면 규칙에 맞는 로직을 쉽게 구현할 수 있다.

 

 

 

답안 코드

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

public class Main {
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        if (N <= 7) { // 규칙에 해당하지 않는 부분 처리
            if (N == 3 || N == 5) System.out.println(1);
            else if (N == 6) System.out.println(2);
            else System.out.println(-1);
            return;
        }
        dp = new int[N + 1];
        dp[3] = dp[5] = 1;
        dp[1] = dp[2] = dp[4] = dp[7] = -1;
        count(N);
        System.out.println(dp[N]);
    }

    static int count(int n) {
        if (dp[n] == 0) {
            if (dp[n - 5] != -1 && dp[n - 3] != -1) {
                dp[n] = Math.min(count(n - 5), count(n - 3)) + 1;
            } else if (dp[n - 5] != -1 && dp[n - 3] == -1) {
                dp[n] = count(n - 5) + 1;
            } else if (dp[n - 5] == -1 && dp[n - 3] != -1) {
                dp[n] = count(n - 3) + 1;
            }
        }
        return dp[n];
    }
}

 

 

 

로직이 복잡하지 않아 쉽게 이해가 갈 것이다.

 

-1 값을 처리하는 부분은 각자가 최적화 하는 방법이 다를 테니 스타일에 맞게 구현하면 된다.

 

 

 

끝