설탕 배달

백준 2839번 그리디 알고리즘

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

문제

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

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

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

입력

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

풀이

만약 18이 들어온다면 5 * 3, 3 * 1 의 합으로 4개의 봉지가 최소값이 된다. 이 알고리즘을 구현하면 되는 문제다.

처음에는 거스름돈을 최소갯수로 거슬러주는 문제처럼 생각하고 알고리즘을 생각해봤다.

• n을 5로 나눈 후 몫을 cnt에 저장한다.

• 5로 나눈 나머지에서 다시 3으로 나누어 나머지가 있는지 확인한다.

• 나머지가 있다면 -1 을 return, 없다면 몫을 cnt에 더한다.

n = int(input())

def solution(n) :
    count = 0

    if n % 5 == 0 :
        count = n // 5
        return count

    if n % 5 != 0 :
        if (n % 5) % 3 == 0:
            count = (n % 5) + (n % 5)//3
            return count

    if n % 5 != 0 and n % 3 == 0 :
        count = n // 3
        return count

    count = -1
    return count

print(solution(n))

하지만 이 생각에는 큰 오류가 있었는데, 예를 들어 16의 경우는 분명히 5와 3 으로 나누어서 가져갈 경우 4개의 봉지갯수를 돌려줘야하는데 위와 같은 방식으로는 무조건 5로 나누게 되므로 나머지가 1이되어 -1을 항상 돌려주게 된다.

그래서 나누는 방식이 아닌 전체 무게에서 5와 3을 봉지에 담아 덜어간다는 생각으로 접근해보기로 했다.

• 반복문을 돌며 n이 5의 배수인지 확인한다. (최솟값 확인)

• 맞다면 그대로 몫을 리턴하고 반복문을 종료한다. 아니라면 n이 3의 배수인지 확인한다.

• 맞다면 n = n - 3 을 실행하고, 아니라면 n = n - 5 를 실행한 후 각각 count(봉지의 갯수)를 +1 한다.

• 반복문을 n > 0 일 때까지 루프를 돈다.

• n < 3 or n == 4 일 경우 count = -1 를 해준 후 바로 반복문을 종료한다.

n = int(input())

def solution(n) :
    count = 0

    while n > 0 :
        if n < 3 or n == 4:
            count = -1
            break

        if n % 5 == 0:
            count += n // 5
            break
        elif n % 3 == 0:
            n -= 3
            count += 1
        else:
            n -= 5
            count += 1

    return count

print(solution(n))

겨우겨우 문제를 해결할수는 있었지만 항상 알고리즘은 JS로 풀다가 파이썬으로 해결하려니 코드가 파이썬스럽지 못하다는 느낌을 지울 수가 없다 ㅠ

문제를 해결하고 기왕 파이썬을 공부중인데 코드를 더욱 파이썬스러운 방식으로 개선하기 위해서 다른 사람들의 풀이를 살펴보았다.

num = int(input())

bag = 0
while num >= 0: # 0이 입력으로 들어올 경우 -1 을 출력시키지 않아야한다.
    if num % 5 == 0:
        bag += num // 5
        print(bag)
        break
    num -= 3
    bag += 1
else:
    print(-1)

여러 코드들이 있었지만 이 코드가 가장 깔끔하다는 생각이 들어서 가져와봤다.

(특별한 파이썬의 문법이 있지는 않지만...)

while 을 else 와 함께 사용해서 while 조건에 걸려들지 않으면 전부 -1 을 출력하도록 한 점이 인상깊다. 그리고 나는 5의 배수가 아니면 3의 배수인지 체크해서 -3 또는 -5 를 한 후 다시 루프를 돌며 체크하도록 했지만, 이 코드는 기본적으로 5의 배수만 체크하고 항상 -3 을 하여 로직을 간소화하였다. 어차피 5의 배수가 아니였는데 -5를 한다한들 5의 배수에 걸릴리가 없기 때문이다.

이렇게 간단한 탐욕법 문제를 하나 풀어보았다. 해결하기 어려운 문제는 아니였지만 파이썬을 좀 더 깔끔하게 쓰고 불필요한 로직을 없애도록 연습할 필요가 있겠다.