[백.단.풀.2] 설탕 배달 (2839)

Step : <사칙연산 도전하기>

Title : " 설탕 배달 "

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	20223	4786	4008	27.398%

문제

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

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

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

입력

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

출력

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

예제 입력 

18

예제 출력 

4

이번 문제는 백준에서 "사칙연산 도전하기" 의 마지막 문제로 나와있었는데

사칙연산 보다는 DP 로 접근을 해서 푸는 것이 아닌가 라는 생각이 들었다.

(사실 사칙 연산으로 어떻게 접근 가능한지 생각조차 안해보고 바로 DP로 풀었음..;;)

음.. DP 라는 것은 나중에 시간이 나면 정리할 생각인데 요약하여 3줄로 정리하자면

다이나믹 프로그래밍 (DP) 3줄 요약

1. 다이나믹 프로그래밍은 답을 재사용하는 알고리즘이다.

2. 다이나믹 프로그래밍을 사용하면 속도가 획기적으로 빨라진다.

3. 결과값을 저장해두는 배열은 결과값으로 나오지 않는 수로 초기화하고, 입력값을 배열이 감당할 수 있게 해야 한다.

라는 알고리즘 해결 기법이다.

즉, 예전에 구했던 답을 사용해서 그 다음 상황에서 답을 구하고자 할 때 빠르게 답을 구하기 위해

그 전에 구했던 답에서 추가적으로 계산을 하는 것이 DP 의 기본 개념이다.

이 문제에서는 3kg 과 5kg 의 봉지를 만드는데, 서로 겹칠 수도 있고 만드는 것이 불가능할 수도 있다는 개념이 들어간다.

그렇게 때문에

문제에서 최대 Input 인 5000 크기의 1차원 배열을 하나 만들어서

그 내부에 3과 5를 사용해 최소로 만들 수 있는 물건들을 미리 구해놓았다.

방법은 아래와 같다.

배열을

arr[5001]

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .................. 5000

0 0 0 1 0 1 0 0 0 ..................................................... 5000

으로 미리 정의를 해놓고, 5000까지 반복문을 돌리며 -3 과 -5 의 값이 0이 아닌 수라면 그 수에서  +1 을 해서 현재 자신의 값으로 정한다.

여기서 예외처리를 해준 것은 -3과 -5 둘다 0이 아닌 경우, 즉, 둘 모두에서 가져올 수 있는 경우이면 그 중 작은 값에서 +1을 해서 가져오도록 설정했다.

그렇게 되면 5000 번을 반복하고 나서, 배열의 모든 값들은 최소로 만들 수 있는 경우로 가득 차게 되고, 받아온 N 번째 배열에 있는 수를 그냥 출력하기만 하면 답이 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <malloc.h>   int N; int arr[5001];   void InitDp() {     arr[3] = arr[5] = 1;       for (int i = 5; i <= 5000; i++)     {         if (arr[i - 3] != 0 && arr[i - 5] != 0)         {             if (arr[i - 3] < arr[i - 5])                 arr[i] = arr[i - 3] + 1;             else arr[i] = arr[i - 5] + 1;         }         else if (arr[i - 3] != 0 && arr[i - 5] == 0)             arr[i] = arr[i - 3] + 1;         else if (arr[i - 5] != 0 && arr[i - 3] == 0)             arr[i] = arr[i - 5] + 1;     } }   int main() {     InitDp();       scanf("%d", &N);          if (arr[N] == 0)         printf("%d", -1);     else         printf("%d\n", arr[N]);       return 0; }