[Python] 백준/BOJ - 2839번: 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1

18

 

예제 출력 1

4

 

My Solution

 

예를 들어 예제 입력 5의 값 11같은 경우 5 * 1 + 3 *2 = 11로 답이 3이 나와야 하는데 이것을 어떻게 처리해줄지가 고민이었다. 따라서 큰 값인 5를 n에서 차례로 5*0, 5*1을 빼주고 남은 값을 3으로 나눠 나누어 떨어지는지를 판별하는 식으로 계산을 해주었다.

 

n = int(input())
a = 5
b = 3

if n < a and n % a == 0:
    print(n // a)
else:
    tmp = 5000
    for i in range(n // a + 1):
        if (n - a * i) % b == 0:
            tmp = min(tmp, i + (n - a * i) // b)
    if tmp != 5000:
        print(tmp)
    else:
        print(-1)

 

먼저 n이 5로 나눠진다면 바로 그 몫을 출력해주고(이 경우가 결과값이 가장 작은 경우이기 때문), 그게 아니라면 n에서 5*i만큼 뺀 후 3으로 나눠진다면 그 값을 tmp에 저장하도록 한다. tmp에 값을 저장할 때는 기존의 tmp값과 새로 나온 결과값을 비교해 작은값을 넣어준다. for문이 끝난 후에 tmp값이 바뀌어있다면(5와 3으로 나눠졌다면) tmp를 출력해주고, 나눠지지 않았다면 -1을 출력해준다.

 

 

어떻게든 풀긴 했지만 찾아보니 좋은 풀이가 있었다. 코드를 보고나니 처음 그리디 알고리즘을 공부했을 때 있던 예제와 비슷한 문제라는 게 생각났다. (복습은 꾸준히 하는걸로..!)

Best Solution

n = int(input())

result = 0

while n >= 0:
    if n % 5 == 0:
        result += n // 5
        print(result)
        break
    n -= 3
    result += 1
else:
    print(-1)

n이 0보다 크거나 같으면 계속 반복문을 돌리며 조건을 체크한다. n이 5로 나누어떨어진다면 그 때의 몫을 result에 더해주고 result를 출력한 후 break해준다. (break를 안써주면 else에 있는 print(-1)도 같이 실행된다.)

n이 5로 나누어떨어질 때까지 3을 계속 빼주고, 빼줄때마다 result에 +1해준다. while문의 조건이 false가 되었는데도 나누어떨어지지 않은 경우에는 -1을 출력해준다.

 

 

ㅠ..