문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
1) 큰 수부터 차례대로 나누기(실패)
거스름돈 문제처럼 가장 큰 수 5로 최대한 나눈 후 나머지를 3으로 나눠서 해결하려고 하였다.
알고리즘
- N 을 입력 받기
- N 을 5로 나눠서 몫을 result에 저장하기
- 5로 나눈 나머지를 N에 다시 저장하기
- N 을 3으로 나눈 몫을 result에 더하기
- 3으로 나눈 나머지가 있다면 result = -1
- result 출력
코드
N = int(input())
result=0
for i in [5,3]:
result += N//i
N = N % i
if N>0 :
print(-1)
else :
print(result)문제 발생
입력이 11일 때,
5로 나눈 후 나머지는 1이 되어 결과가 -1로 나온다.
하지만, 실제로는 (5+3+3)으로 결과는 3이 나와야 한다.
무조건 큰 수로 먼저 나누는 것은 안되는 결과가 나왔다.
이유는 5가 3의 배수가 아니라서 3의 배수를 완전히 커버할 수 없기 때문이다.
그리디 알고리즘 문제를 풀 때 가장 흔히 하는 실수다.
해결
3을 하나씩 늘려가면서 5로 나누어 떨어지는지 확인하는 방법을 사용하기로 하였다.
2) 3의 개수를 하나씩 늘려가기(성공)
알고리즘
- N을 입력 받는다
- N 에서 3 * i를 뺀다.(i는 0 ~ N//3)
- 뺀 결과가 0이거나 5로 나누어지는지 확인한다
- 맞다면 result에 i+(N-3*i)//5를 저장하고 출력, N = 0.
- 아니라면 i를 1늘려 반복한다.
- 반복이 끝나고 N>0 이라면 -1출력
코드
N = int(input())
result=0
for i in range(N//3 +1):
if (N - 3*i)<0:
break
if (N - 3*i)==0 or (N - 3*i)%5 == 0:
result += (i+((N - 3*i)//5))
N=0
print(result)
if N>0 :
print(-1)복잡도
이 코드의 복잡도는 반복문을 주목하면 되는데, 반복문이 N/3 번 반복되기 때문에 O(N) 이라고 할 수 있다.
결론
그리디 알고리즘 카테고리에서 문제를 선택했기 때문에 당연히 가장 큰 수부터 나눠야 
할 것이라고 생각했다.
중간에 3과 5의 최소공배수로도 나눠보고, 5를 하나씩 늘리는 방법도 시도했으나 반례에 부딪혔다.
그리디 문제를 풀 때 배수관계에 대해서 주의깊게 살펴야겠다.
쉬운 문제지만 혼자 힘으로 풀어냈다는 점이 뿌듯하다.
끝.
