문제
https://www.acmicpc.net/problem/2839
N kg의 설탕을 배달하기 위해, 3kg, 5kg을 담을 수 있는 주머니를 사용할 수 있다. 운반에 필요한 최소 주머니 개수를 구하라
ex) 18kg의 경우 3kg 6개도 되고 5kg 3개, 3Kg 1개 총 4개도 가능하다.
접근 방식
그리디 방법이라고 해서, 일단 모든 경우의 수를 다 탐색을 해야겠다고 생각했습니다. 그래서 쉽게 구현할 수 있는 재귀 호출을 이용해서, 3kg, 5kg일때 각각 경우의 수에 대해서 조사를 합니다.
(풀이1)
| 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define P1 3 5 #define P2 5 6 7 void find(int N, int depth, int *answer) 8 { 9 if (depth == *answer) 10 return; 11 12 if (N == 0) 13 { 14 if (*answer > depth || *answer == -1) 15 { 16 *answer = depth; 17 } 18 return; 19 } 20 21 if (N >= P1) find(N - P1, depth+1, answer); 22 if (N >= P2) find(N - P2, depth+1, answer); 23 } 24 25 26 int main(int argc, char* argv[]) 27 { 28 int N=0; 29 int answer = -1; 30 fscanf(stdin, "%d", &N); 31 32 find(N, 0, &answer); 33 fprintf(stdout, "answer = %d\n", answer); 34 return 0; 35 } |
결과는 timeout입니다. 18의 경우, 5-5-5-3 이렇게 4가지를 구하면 되는건데, 이렇게 재귀호출로 모든 경우의 수를 조사하면 5-5-3-5, 5-3-5-5, 와 같이, 계산하지 않아도 될 path를 모두 탐색하는 형태가 되어버리네요. N이 작은 경우에는 정답이 나오긴 합니다.
(정답과 상관없이 시행착오를 기술하고자 하는 목적도 있어서, 정답과는 거리가 멀지만 적어두겠습니다.)
풀이2)
그냥 직관적으로 효율적인 방법을 생각해봤을 때, 5kg짜리 가방을 모두 소진하고, 남는 3kg가방을 사용하는 것이 베스트 일 것입니다. 나머지 연산을 통해서 5kg이 딱 들어가는지 여부를 체크하고, 아닐 경우에는 3kg짜리 가방을 하나씩 소진해가면서 5kg짜리 가방을 사용할 수 있을지 계속 판단해보면 됩니다.
N=20 // 5로 나누어떨어지므로, 5kg짜리만 사용합니다.
5-5-5-5
N=23 // 23 % 5 != 0 이므로, 3kg짜리 하나를 소비하고 N=20이 되었을 때 5kg짜리 가방을 사용합니다.
3-5-5-5-5
| 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int main(int argc, char* argv[]) 5 { 6 int N = 0, i = 0; 7 int answer = 0; 8 fscanf(stdin, "%d", &N); 9 10 while(1) 11 { 12 if (N % 5 == 0){ 13 answer += (int)(N/5); 14 break; 15 } 16 N -= 3; 17 answer++; 18 if (N < 0) 19 { 20 answer = -1; 21 break; 22 } 23 } 24 fprintf(stdout, "answer = %d\n", answer); 25 return 0; 26 } |
회고
greedy라고 해서 무조건 경우의 수를 다 뒤진다고 생각하면 안될 것 같습니다. 적당히 탐색하다가 탐색하지 않아도 되는 조건을 발견해서 최적화를 하면 될 것이라고 생각했는데, 아예 방향성부터 잘못 잡게 되면 최적화단계는 아무 의미가 없다는 것을 느꼈습니다.