[Baekjoon] 2839번 설탕배달
설탕 배달
| 시간 제한 | 메모리 제한 | 정답 비율 |
|---|---|---|
| 1초 | 128MB | 34.418% |
문제
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)
출력
상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.
예제 입출력
| “Input” | “Output” |
|---|---|
| 18 | 4 |
| 4 | -1 |
| 6 | 2 |
| 9 | 3 |
| 11 | 3 |
문제 풀이
이 문제는 백준 단계별 풀이 기본수학1의 7단계 문제로 쉽게 풀릴 줄 알았으나 꽤 오래 헤맨 문제였습니다. 알고리즘이 수학, 다이나믹 프로그래밍, 그리디 알고리즘로 분류 되어 있었는데 이 중 수학을 제외하고는 아직 학습이 진행 되지 않은 상태였기 때문에 구현 방식을 떠 올리기가 쉽지 않았던 것 같습니다.
풀이 구상
처음에 이 문제를 보고
- N이 5로 나누어 떨어지는 경우
- N이 3으로 나누어 떨어지는 경우
- N이 3과 5 둘 중 어느 것으로도 나누어 떨어지지 않지만 둘 중 어느 것으로 나누었을 때 나머지가 나눈 숫자와 다른 숫자(3으로 나누었으면 5, 5로 나누었으면 3)가 나머지로 나오는 경우
등등 의 경우가 떠올랐습니다.
5로 나누어 떨어지는 숫자의 경우 5로 나눈 몫이 가장 적은 수 일 것이기 때문에 따로 구별 해 두어야 할 것 같았고 그것과 그 이외의 case를 나누고 이 case에서 또 세부적으로 나누어야 겠다고 생각했습니다.
그래서 if문을 통해 각 case를 나누어 결과 값을 도출 하려 해보았습니다. 그러나 이렇게 하면 ‘18’ 같은 숫자의 경우 3으로도 딱 나누어 떨어지지만 5랑 3을 섞어서 나누었을 때 더 적은 봉지 수가 나오므로 이에 대한 예외처리를 하기가 힘들었습니다.
그러던 중 노트에 이 문제가 원하는 핵심 공식을 적어보다가 아이디어가 딱 떠올랐습니다.
그 공식은 바로 방정식을 활용한 식으로 다음과 같습니다.
5x + 3y = N
x는 5kg의 봉지 수를 나타내고 y는 3kg의 봉지 수를 나타냅니다. 이 공식을 보고 저는 이중 for문을 돌려서 x, y에 값을 하나씩 넣어 보면서 이를 더하였을 때 N이 나오는 경우를 찾고 리스트에 추가하면서 그 중 가장 작은 숫자를 선택하면 되겠다고 생각했습니다.
그러기 위해서 다음과 같은 문제들을 처리해야 했습니다.
- 각 for문을 돌리는 횟수는 어떻게 정할 것인가?
- 만약 18이라는 숫자를 가정하여 본다면 x는 0보다는 크고 4보다는 작아야 하며 y는 0보다 크고 6보다 작아야 합니다. 그런데 이는 18이라는 숫자를 3과 5로 각각 나누었을 때 떨어지는 몫들과 관련이 있는 것이기 때문에 각각 mok_5와 mok_3 이라는 변수에 저장을 하여 이를 for문의 횟수로 하였습니다.
mok_5 = N // 5
mok_3 = N // 3
for y in range(mok_3+1):
for x in range(mok_5+1):
- 식을 만족 하는 x,y의 쌍이 여러 개가 나오면 어떻게 할 것인가?
- 사실 처음에는 x와 y 각각을 리스트에 append 하여 그 두개의 합을 더하여 결과를 도출하려 했으나 리스트를 출력해 본 결과 여러 쌍이 나올 수 있다는 것을 깨달았고 이를 그러면 각 x와 y를 더한 값을 리스트에 append하는 것으로 해결하면 될 것이라 생각했습니다.
if x*5 + y*3 == N:
list_a.append(x+y)
- 식을 만족하지 않아 -1을 출력해야 하는 경우는 어떻게 처리 할 것인가?
- 이 경우는 식을 만족하는 x와 y가 없으면 이 둘의 합 또한 리스트에 append가 되지 않았을 것이기 때문에 이는 len()함수를 활용하여 리스트의 길이가 0이면, 즉 리스트가 비어있으면 -1을 출력하는 것으로 쉽게 해결할 수 있었습니다.
if len(list_a) == 0:
print(-1)
else:
print(list_a[0])
최종적으로 리스트에 append된 값들 중 가장 적은 수를 찾아내는 것이 이 문제의 결과이기 때문에 리스트를 오름차순으로 정렬하여 리스트의 첫번째 값을 불러오면 그것이 최종 결과가 되는 것입니다.
전체 코드
N= int(input())
list_a = []
mok_5 = N // 5
mok_3 = N // 3
for y in range(mok_3+1):
for x in range(mok_5+1):
if x*5 + y*3 == N:
list_a.append(x+y)
list_a.sort()
if len(list_a) == 0:
print(-1)
else:
print(list_a[0])
댓글남기기