[백준][2단계][2839번] 설탕 배달 (Java) : 동적 계획법, 함정문제(?)

 * 오류 지적, 오타, 내용 개선 댓글은 대환영입니다!

 * 본론만 원하신다면 문제 탭까지 내리시면 됩니다.

 * 해당 글은 PC에 최적화되어 있습니다.

 안녕하세요, 갓벨입니다. 오랜만에 찾아뵈었습니다. 입시 서류도 제출했고, 추석도 지났고, 이제 면접을 기다리는 일만 남았군요. 아, 번역도...^^ 

 2단계 문제도 벌써 마지막 문제군요. 이번 게시글부터 설명을 이전과는 조금 다르게 할 생각입니다. 사실 하도 오랫동안 손을 못 대고 있다 보니까 변한 것도 있지만...요...

 한번 문제를 보니까 이번 문제, 뭔가 깁니다. 문제에 스토리가 있습니다. 수학 문제를 풀 때처럼, 읽으면서 풀이를 떠올려 보았습니다. 그런데 개인적인 느낌입니다만, 2단계에서 여태까지 다뤘던 문제들과는 꽤 다른 난이도였습니다. 단순한 문제였지만, 동시에 꽤 어렵기도 한 문제였습니다. 아이디어를 조금 내야 하는 문제였죠.

...이거 이렇게 푸는 거 맞나?

 

 저는 이 문제를 동적 계획법을 이용해서 풀었습니다. 학교 수행평가로 인공지능 정보길잡이가 되어 버린 제 예전 블로그에 올려 놓은 [동적 계획법]에 대한 내용을 참고하신다면 도움이 될 겁니다. 도저히 잘 쓴 글이라고 부를 순 없는 글이지만 말이죠. 이 글은 나중에 재구성을 해서 다시 올려 보겠습니다.

 동적 계획법을 이용한 방법보다 쉬운 방법은 많습니다. 구글링 해보시면 그리드나 단순 반복문 사용으로 문제를 해결하는 방법이 많이 나옵니다. 심지어 BOJ 풀이 목록에 정수 법칙인가를 이용해 푸는 방법도 소개되어 있는 듯하던데, 가장 최근에 공부한 게 동적 계획법이라 그런지 저는 동적 계획법부터 떠오르더군요;; 프로그램 효율 면에서는 좋긴 합니다.

 동적 계획법이 어떤 식으로 사용되는지, 대충 어떤 건지 알고 싶다! 혹은 동적 계획법으로 이 문제를 어떻게 풀까 하시는 분들에게 추천합니다.

문제

 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 

 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

예제 입력

18

* 예제는 하나만 써 놓겠습니다.

예제 출력

4

답안

 다음은 코드 전문입니다. 풀이는 아래에 있습니다.

import java.util.Scanner;

class Main
{
    public static void main(String args[])
    {
        //while(true) { //테스트용 무한루프

            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();

            int[] dynamic = new int[N + 1];
            int[] defaultab = {-1, -1, -1, 1, -1, 1, 2, -1};

            if (N <= 7) {
                System.out.println(defaultab[N]);
                return;
            }
            else
                for (int i = 0; i <= 7; i++)
                    dynamic[i] = defaultab[i];

            for (int i = 8; i <= N; i++)

                if(dynamic[i-5] != -1 && dynamic[i-3] != -1)
                    dynamic[i] = 1 + Math.min(dynamic[i - 3], dynamic[i - 5]);

                else if(dynamic[i-5] == -1 && dynamic[i-3] != -1)
                    dynamic[i] = 1 + dynamic[i-3];

                else if(dynamic[i-5] != -1 && dynamic[i-3] == -1)
                    dynamic[i] = 1 + dynamic[i-5];

            System.out.println(dynamic[N]);

        //}
    }
}

 

풀이

 3과 5로 만들 수 없는 경우는 -1을 출력해야 합니다. 근데 3과 5로 만들 수 없는 경우가 뭐가 있을까요? 일단 3부터 한 20 정도까지, 최소한 몇 번의 계산을 거쳐야 3-과 5를 이용하여 만들 수 있는지 세어 봅시다. X는 만들 수 없는 경우입니다.

 

숫자	1	2	3	4	5	6	7	8	9	10
계산 횟수	X	X	1	X	1	2	X	2	3	2
식	X	X	3		5	3+3		3+5	3+3+3	5+5

 

11	12	13	14	15	16	17	18	19	20
3	4	3	4	3	4	5	4	5	4
3+3+5	3+3+3+3	3+5+5	3+3+3+5	5+5+5	3+3+5+5	3+3+3+3+5	3+5+5+5	3+3+3+5+5	5+5+5+5

 일부러 20까지 직접 세어 보았습니다. 더 적게 세어 봐도 상관은 없습니다. 세고 나서 보니까, 8, 9, 10이 모두 계산 가능하다면, 11, 12, 13, ... 은 당연히 전부 계산 가능하겠군요. 결국 만들 수 없는 수는 4와 7뿐입니다. 4와 7을 출력할 때만 -1을 출력하도록 하면 되겠군요.

---

 동적 계획법을 이용해 점화식을 세워야 하는데, 고민입니다. 문제에 제시되었다시피 N의 최댓값은 5000씩이나 되니까 끝까지 하나하나 입력해서는 도저히 안 됩니다. 위 표를 보면서 더 좋은 방법을 찾아 봅시다. 규칙이 있는지 봐야겠습니다.

 아무 숫자나 하나 잡아 봅시다. 20으로 해 볼까요?

 

숫자	15	17	20
계산 횟수	3	5	?
식	5+5+5	3+3+3+3+5	?

 

 20을 만들기 위해서는 15에 5를 더하거나 17에 3을 더해야 합니다. 그런데 위 과정을 보면, 굳이 여섯 번 계산해서3+3+3+3+5에 3을 더해서 20을 만드느니, 네 번만 계산해서 5+5+5에 5 하나 더하는 게 횟수가 더 적습니다. 그래서 20을 만드는 데 필요한 최소 횟수는 4입니다. 동적 계획법은 이렇게 적용됩니다. 20을 만드는 횟수가 최소이려면, 그 중간 과정의 수를 만드는 횟수도 최소가 되어야 하는 거죠.

 앞의 수도, 뒤에 나올 수많은 수들도 똑같이 적용됩니다. 아참, 이런 경우도 있습니다.

숫자	5	7	10
계산 횟수	1	X	?
식	5	X	?

 

 애초에 7은 만들어지지 않습니다. 그러니까 7에 3을 더해 10을 만드는 건 불가능하다는 거죠. 이

때는 그냥 5에 5를 더해 10을 만들면 됩니다. 그래서 계산 횟수가 2번인 거죠. 

 정리하면 어떤 수에 대해 최소 계산 횟수를 알아내고자 한다면 자, 이제 점화식이 보이실 겁니다.

 

 p(n)은 해당 수를 만들기 위해 3과 5를 사용하는 최소 횟수, min은 쉼표로 구분된 두 수 중 작은 값을 고른다는 뜻입니다. 1부터 7까지는 위 표의 값을 그냥 입력하고 8부터 이 식을 적용하면 되겠습니다. 조건문 쓰기 싫다 하시는 분은 13부터 적용하셔도 괜찮겠네요.

 크기가 N+1인 배열(배열 인덱스가 0부터 시작하므로)을 하나 선언합시다. 7번째 값까지는 미리 입력합시다. 만들 수 없는 수는 -1을 출력해야 하니 0,1,2,7번째에는 -1을 넣어 둡시다. 저는 다음과 같은 방식으로 했습니다.

int[] dynamic = new int[N + 1];
int[] defaultab = {-1, -1, -1, 1, -1, 1, 2, -1};

if (N <= 7) {
    System.out.println(defaultab[N]);
    return;
    }
else
    for (int i = 0; i <= 7; i++)
        dynamic[i] = defaultab[i];

 dynamic이라는 정수 배열에 defaultab배열에 미리 저장해 놓은 값들을 저장하게 합니다. N이 7보다 작거나 같을 때는 그냥 defaultab에 저장된 값을 출력하게 하고 프로그램을 끝냅시다. 이제 배열의 dynamic[8]부터 다음과 같이 점화식을 적용하면 됩니다.

for (int i = 8; i <= N; i++)

    if(dynamic[i-5] != -1 && dynamic[i-3] != -1)
          dynamic[i] = 1 + Math.min(dynamic[i - 3], dynamic[i - 5]);

    else if(dynamic[i-5] == -1 && dynamic[i-3] != -1)
          dynamic[i] = 1 + dynamic[i-3];

    else if(dynamic[i-5] != -1 && dynamic[i-3] == -1)
          dynamic[i] = 1 + dynamic[i-5];

 그 뒤에 dynamic[N]을 출력하도록 하면 됩니다. 

---

 다음 문제에서 봅시다! 다음 문제부터는 3단계군요.