1. 문제 요약
설탕을 담을 수 있는 봉지의 종류가 3kg과 5kg짜리 두 개인데,
어떻게 하면 입력받은 무게를 최소의 봉지 수를 사용하여 담을 것인가?
예) 18 = 5 + 5 + 5 + 3 (output: 4) = 3 + 3 + 3 + 3 + 3 + 3 (output: 6) 이런 경우에 4를 출력
2. 처음 풀이
처음엔 수업시간에 풀었던 문제 중에 비슷한 문제가 생각나서 pick이라는 재귀함수를 만들어서 풀었다.
배운대로라면 bucket을 만들어야 하는데 그렇게 만들면 시간이 초과될 것 같아 없앴는데,
그래도 파일 크기가 너무 크고 시간 초과가 된다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void pick(int* item, int N, int k, int cnt, int* min) // min: 최소 개수, k: 남은 무게
{
int i;
if (k < 0) {
return;
}
if (k == 0) {
if (cnt < *min)
*min = cnt;
return;
}
for (i = 0; i < 2; i++) {
pick(item, N, k - item[i], cnt + 1, min);
}
}
int main(void)
{
int N, min;
int item[2] = {5, 3};
scanf("%d", &N); // N 킬로그램 입력 받기
if (N < 3 || N > 5000) {
printf("-1\n");
return 0;
}
min = N / 3 + 1;
pick(item, N, N, 0, &min);
if (min == N / 3 + 1) printf("-1\n");
else printf("%d\n", min);
return 0;
}
3. 마지막 풀이
이 문제의 핵심 아이디어는 최소한의 봉지를 사용하려면 5kg짜리를 최대한 사용해야 한다는 것이다.
그래서 두 예시를 들며 생각해 보았다.
쉬운 예시)
3과 5를 곱해서 만들어진 수인 15를 생각 했을 때 얻을 수 있는 최소 값을 생각해보면 5kg짜리 봉지만을 사용했을 때이다.
소인수 분해로 생각했을 때)
45 = 3 x 3 x 5 >> 3kg(3 x 5), (3 x 3)5kg 여기서 볼 수 있듯이 용량이 큰 봉지로 묶었을 때 필요한 봉지 수가 더 적어진다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int N, cnt = 0;
scanf("%d", &N);
if (N < 3 || N > 5000) return 0;
while (1) {
if (N % 5 == 0) {
cnt += N / 5;
N %= 5;
break;
}
cnt++;
N -= 3;
if (N <= 0) break;
}
if (N == 0) printf("%d\n", cnt);
else printf("-1\n");
return 0;
}내가 했던 첫 번째 착각은 모든 경우의 수를 구해서 그 중에서 최소 값을 찾는게 아니라,
한번에 최소값을 찾을 수 있는 문제였다는 것이다.
