Python) 2839번 설탕 배달 문제

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

 

Python) 백준 2839번 - 설탕 배달 문제 풀이

오늘은 백준 2839번 문제인 설탕 배달 문제를 Python으로 풀어보겠습니다. 이 문제는 정해진 크기의 설탕 봉지를 사용해 정확한 무게를 배달하는 최소 봉지 수를 구하는 문제입니다.

---

문제 설명

설탕 공장에서 제공하는 봉지는 5kg와 3kg짜리 봉지가 있습니다. 우리는 정확히 N kg의 설탕을 배달해야 합니다. 이때 설탕 봉지를 최소한으로 사용하여 배달할 수 있는 방법을 찾아, 사용된 봉지의 수를 출력하세요. 만약 정확히 N kg의 설탕을 배달할 수 없다면, -1을 출력합니다.

입력

• 첫째 줄에 N이 주어집니다. (3 ≤ N ≤ 5000)

출력

• 설탕을 정확하게 N kg 배달할 수 있다면, 봉지의 최소 개수를 출력합니다.
• 불가능하다면 -1을 출력합니다.

---

문제 해결 과정

이 문제는 N kg의 설탕을 5kg 봉지와 3kg 봉지를 사용해 담을 수 있는 최소 봉지 수를 찾는 문제입니다. 우리는 가능한 많은 5kg 봉지를 사용하고, 나머지 무게는 3kg 봉지로 채우는 방식으로 해결할 수 있습니다.

🔍 핵심 개념

• 5kg 봉지를 먼저 사용할 수 있는 만큼 사용하고, 나머지 무게를 3kg 봉지로 나누어 떨어지도록 해야 최소 봉지 수를 구할 수 있습니다.
• 설탕 무게가 5와 3으로 나누어떨어지지 않는 경우, 적절히 봉지 개수를 줄여야 합니다.

---

💡 풀이 전략

1. 먼저 5kg 봉지로 나누어 떨어지는지 확인합니다. 만약 나누어떨어지면 바로 그 개수를 출력합니다.
2. 그렇지 않다면 3kg 봉지를 하나씩 추가하면서 5kg 봉지로 나누어떨어지는지 반복해서 확인합니다.
3. 만약 3kg 봉지를 추가하면서도 나누어떨어지지 않는 경우, 설탕을 배달할 수 없기 때문에 -1을 출력합니다.

---

🔨 코드 구현

방법 1: 반복문을 사용한 풀이

kg = int(input())

if kg % 5 == 0:  # 5으로 나눠떨어질 때
    print(kg // 5)
else:
    three_bag = 0
    while kg > 0:
        kg -= 3
        three_bag += 1
        if kg % 5 == 0:  # 3kg과 5kg를 조합해서 담을 수 있을 때
            five_bag = kg // 5
            print(three_bag + five_bag)
            break
        elif kg == 1 or kg == 2:  # 설탕 봉지만으로 나눌 수 없을 때
            print(-1)
            break
        elif kg == 0:  # 3으로 나눠떨어질 때
            print(three_bag)
            break

방법 2: 조건문을 활용한 간단한 풀이

kg = int(input().strip())

if kg == 7:
    print("-1")
elif kg < 5:
    if kg == 3:
        print("1")
    else:
        print("-1")
else:
    five_bag = kg // 5
    if kg % 5 == 0:
        print(five_bag)
    elif kg % 5 == 3:
        print(five_bag + 1)
    elif kg % 5 == 1:
        print((five_bag - 1) + ((kg - (5 * (five_bag - 1))) // 3))
    elif kg % 5 == 2:
        if kg == 12:
            print(4)
        else:
            print('-1')
    elif kg % 5 == 4:
        print((five_bag - 1) + ((kg - (5 * (five_bag - 1))) // 3))

---

🚀 코드 설명

방법 1

• 5kg으로 나누어 떨어질 때까지 반복문을 사용합니다.
• 매번 3kg을 빼면서 5kg으로 나눠떨어지면, 3kg 봉지와 5kg 봉지의 수를 더하여 최소 봉지 수를 출력합니다.

방법 2

• 특정 무게에서 바로 -1을 출력할 수 있는 예외 상황을 처리한 후, 나머지 경우에 대해 5kg 봉지와 3kg 봉지를 조합하여 최소 봉지 수를 계산합니다.

---

🧐 배운 점

이번 문제는 그리디 알고리즘 문제로, 가능하면 큰 단위의 봉지를 먼저 사용한 후, 작은 단위의 봉지로 나머지를 채우는 방식으로 해결하는 것이 중요했습니다. 반복문과 조건문을 사용해 다양한 예외 상황을 처리하며 문제를 해결할 수 있었습니다.

---

🔚 마무리

이 문제는 설탕을 최소한의 봉지로 나누어 담는 그리디 알고리즘의 대표적인 문제입니다. 특히, 문제의 조건을 분석해 특정한 예외 상황을 잘 처리하는 것이 핵심이었습니다. 앞으로도 그리디 알고리즘 문제에서 큰 단위부터 처리하는 방법을 잘 익혀 나가면 좋을 것 같습니다.