(2839) 설탕 배달

문제

문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

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

---

문제 풀이

해당 문제를 그리디 알고리즘이 아닌 DP 알고리즘 방식으로 문제를 해결하고자 하였음. 

먼저 DP에서는 규칙성을 찾는게 우선이다. 현재 3, 5배수에 따른 설탕 배달 횟수가 있어야 하고 킬로그램이 늘어나면서 각 킬로그램마다 옮기는 최적해를 기록하는 것을 어떻게 구현 하는가가 중요하다. 

 

먼저 dp[0] 은 0 으로 초기화를 냅둔 상태에서 시작하는 것이 중요하다. 그 이유는 나중에 나와 있다.

dp[1] 부터는 시작시 Integer.MAX_VALUE로 초기화를 해주고 i - 3 이 0 이상이면서 dp[i-3] != Integer.MAX_VALUE가 아닐 때 까지 반복문을 반복한다. 

 

i = 3 이 되면 아래와 같은 그림이 된다 . (편의상 MAX_VALUE는 -1로 표현)

여기서 dp[3] 들어갈 내용은 dp[ i -3 ] + 1과 dp [3] 에서 더 큰 값이 들어가야 한다. 즉, 1이 들어가게 된다. 여기서 + 1에 대한 이유를 궁금하게 되는데 3의 배수이기 때문에 횟수가 늘어나야 하기 때문에 늘어 나는 것으로 이해 하면 된다. 

5의 배수도 3의 배수와 같다. dp[ i -5 ] + 1과 dp [5] 에서 더 큰 값이 들어가야 한다.

i = 8 이 되면 이제 3과 5에 들어간 값 두개와 같이 비교하게 되는데, 이것이 이제 dp에서 최적해를 구하는 식이 정립되었다고 할 수 있다. 현재 dp[ i - 3 ] = 1 , dp[ i -5 ] = 1 둘 다 같은 값으로 둘 중 아무거나 결과값을 가져와서 + 1만 해주면 된다. 

i = 18 까지 진행을 하면 아래와 같은 모습을 가지게 된다. 

---

나의 답안

private static int solution(int n) {
    int[] dp = new int[n + 1];

    for (int i = 1; i <= n; i++) {
        dp[i] = Integer.MAX_VALUE;

        if (i - 3 >= 0 && dp[i - 3] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[i - 3] + 1);
        }

        if (i - 5 >= 0 && dp[i - 5] != Integer.MAX_VALUE) {
            dp[i] = Math.min(dp[i], dp[i - 5] + 1);
        }
    }

    for (int i = 0; i < dp.length; i++) {
        System.out.println(i + " " + dp[i]);
    }
    return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
}