백준 2839 - 파이썬

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

2839번: 설탕 배달

문제 풀이

이번 문제는 완전 탐색이면서도 그리디 알고리즘과도 연관될 수 있는 문제이다. 주어진 N kg 설탕을 5kg과 3kg 봉지를 활용하여 가장 적은 봉지 수를 찾는 것이다. 그렇기에 문제를 보자마자 가장 큰 수인 5로 나눠지는 수를 찾는 게 이 문제의 핵심이라고 생각되었다. 처음에 떠올린 알고리즘은 5를 반복문이 종료될 때까지 계속 빼주면서 3으로 나눠지는 수를 찾는 것이었다.

T = int(input())
n = T
sugar_list = []

result = 0
if n % 3 == 0:
    sugar_list.append(n // 3)

for i in range(T):
    n -= 5
    if n <= 0:
        break
    result += 1
    if n % 3 == 0:   
        result += n // 3
        n %= 3
        sugar_list.append(result)

if sugar_list:
    print(min(sugar_list))
else:
    print(-1)

 

3으로 한번에 나눠지는 경우와 5를 하나씩 빼주며 3으로 나눠지는 수를 찾아 리스트에 저장해 주고, 리스트에서 가장 작은 수를 출력하도록 한 코드이다. 하지만 이 코드의 제출 결과는 오답이었다. 반례를 찾아보니 168일 때는 34가 나와야 하는데 54가 나왔기 때문이다. 그래서 다시 고민해 보다가 반대로 3부터 빼면서 5로 나눠지는 수를 찾아보면 어떨까 싶어 코드를 다시 짜 봤다.

 

n = int(input())

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

 

정답인 코드를 찾았다. 이번에는 5로 한번에 나눠진다면 가장 적은 봉지 수이기 때문에 리스트에 저장하지 않았다. 대신 맨 아래 조건문을 보면 1이나 2가 나온다면 -1을 출력하도록 해놨는데, 이 경우는 3으로 계속해서 뺏는데도 0이 나오지 않고 1이나 2가 나온다는 것은 답을 찾을 수 없다는 뜻이기 때문에 이렇게 작성했다.

 

다른 사람들은 어떻게 풀었나 궁금하여 찾아봣는데 더 간결하게 작성한 분이 있어서 가지고 와 봤다.

 

sugar = int(input())

bag = 0
while sugar >= 0 :
    if sugar % 5 == 0 :  # 5의 배수이면
        bag += (sugar // 5)  # 5로 나눈 몫을 구해야 정수가 됨
        print(bag)
        break
    sugar -= 3  
    bag += 1  # 5의 배수가 될 때까지 설탕-3, 봉지+1
else :
    print(-1)

 

이 분 역시 5로 나눠진다면 가장 적은 봉지 수이기 때문에 반복문을 탈출해 주고, 그렇지 않다면 3을 계속 빼주는 식으로 작성하였다.

 

느낀 점

이번 문제 역시 생각을 약간 바꾸는 것으로 부족한 2%를 해결할 수 있었는데, 어느 정도 감이 잡혀 풀이가 진행된 문제는 어떻게 사고의 전환을 조금이라도 더 할 수 있는지에 따라 부족한 2%가 채워지는 것 같다. 또한 문제를 풀어내는데 많은 시간이 소요되었지만 그래도 풀었다는 것에 의의를 둔다. 시간도 단축하고 싶지만 이건 꾸준히 계속 풀어본다면 해결될 문제라고 생각된다.