백준 2839번: 설탕 배달 문제 해결 과정 (Python)

🔹 내가 처음 작성한 코드

n = int(input())

five_max = n // 5
three_max = n // 3
best = n  # 최대값으로 설정 (불가능한 경우 대비)

for five_cnt in range(five_max + 1):
    for three_cnt in range(three_max + 1):
        if (five_cnt * 5 + three_cnt * 3) == n:
            if (five_cnt + three_cnt) < best:
                best = five_cnt + three_cnt

if best == n:
    print("-1")  # 정확한 무게를 만들 수 없는 경우
else:
    print(best)

---

✅ 내 코드의 특징과 문제점 분석

✔ 특징

• 완전 탐색(브루트포스) 방식으로 5kg와 3kg의 모든 조합을 확인함.
• 가장 적은 봉지를 찾기 위해 best 변수를 활용함.
• 가능한 모든 조합을 시도하므로 정확한 정답을 보장할 수 있음.

❌ 문제점

1. 불필요한 모든 조합을 탐색 (O(N²))
   • five_cnt와 three_cnt를 모든 조합으로 탐색하는 방식 → 비효율적.
   • 최대 5000×5000 = 2500만 번의 연산이 발생할 수 있음.
2. 더 효율적인 방법이 존재
   • 무게가 N일 때, 항상 5kg을 최대한 먼저 사용하는 것이 최적해를 보장.
   • 따라서 불필요한 모든 경우를 시도할 필요 없음.

---

🔥 최적화된 코드 (O(N))

n = int(input())

bag_count = 0  # 사용한 봉지 개수

while n >= 0:
    if n % 5 == 0:  # 5kg로 정확히 나눠떨어지면
        bag_count += n // 5
        print(bag_count)
        break
    n -= 3  # 5kg로 나눠떨어지지 않으면 3kg 하나 사용
    bag_count += 1
else:
    print(-1)  # 정확한 무게를 만들 수 없는 경우

---

✅ 최적화된 코드의 특징과 장점

✔ 특징

• 5kg 봉지를 최대한 먼저 사용하여 최적해를 보장.
• while 루프를 사용하여 한 방향으로만 탐색 (O(N)).
• 리스트를 사용하지 않으므로 O(1) 공간 복잡도.

🔹 시간 복잡도 비교

코드 방식 시간 복잡도 최악의 경우(N=5000)

브루트포스 (O(N²))	O(N²)	25,000,000번 연산
최적화 코드 (O(N))	O(N)	5000번 연산

📌 ➡ 기존 코드보다 약 5000배 빠름!

---

✅ 실행 예제

입력

18

과정

1. 18 % 5 != 0, 5kg로 나누어떨어지지 않음 → n -= 3
2. 15 % 5 == 0 → 15kg = 5kg x 3
3. 총 봉지 개수 = 3 (5kg) + 1 (3kg) = 4

출력

4

---

🎯 결론

✔ "모든 경우의 수를 탐색하는 방법"보다 "최적의 방법을 먼저 고려하는 것"이 중요!
✔ 5kg 봉지를 최대한 먼저 사용하면 최적해를 보장할 수 있음
✔ 시간 복잡도를 O(N²) → O(N)으로 줄여 훨씬 효율적인 코드 완성!

---

📝 요약

코드 방식 특징 시간 복잡도 비고

초기 코드 (브루트포스)	모든 5kg, 3kg 조합 탐색	O(N²)	매우 비효율적
최적화 코드	5kg을 최대한 먼저 사용	O(N)	🚀 가장 효율적

📌 이제 코딩 테스트에서 "시간 초과"를 피하고 더 효율적인 코드로 해결 가능! 🎯🔥