[백준] 2839번 파이썬 (설탕 배달)

1. 문제와 예제

문제

예제

---

2. 전체 코드

1) 노가다

# 노가다
kg = int(input())

cnt5 = 0
cnt5 = kg // 5
if kg % 5 == 0:
    cnt3 = 0
    print(cnt5 + cnt3)
elif kg % 5 == 1:
    if cnt5 == 0:
        print(-1)
    else:
        cnt5 -= 1
        cnt3 = 2
        print(cnt5 + cnt3)
elif kg % 5 == 2:
    if cnt5 == 0 or cnt5 == 1:
        print(-1)
    else:
        cnt5 -= 2
        cnt3 = 4
        print(cnt5 + cnt3)
elif kg % 5 == 3:
    cnt3 = 1
    print(cnt5 + cnt3)
else:
    if cnt5 == 0:
        print(-1)
    else:
        cnt5 -= 1
        cnt3 = 3
        print(cnt5 + cnt3)

가장 먼저 떠오른 방법이다. 결국 전체 봉지 수를 최소로 가져가려면 5kg 봉지를 최대로 가져가야 한다는 아이디어에서 나온 방법이다. 공통적인 것끼리 묶으면 조금 더 짧게 코드를 만들 순 있겠다.

 

2) 다이나믹 프로그래밍

# 입력 받기
N = int(input()) # 설탕
res = 0 # 봉지

while N >= 0:
    if N % 5 == 0:
        res += (N // 5)
        print(res)
        break
    # 5로 나눠지지 않았을 때
    N -= 3
    res += 1 # 3kg 봉지 하나 추가
else: # while문에서 else가 나왔을 때
    print(-1)

1번 방법을 응용하면 다이나믹 프로그래밍이라는 개념이 나온다. 동적계획법이라고도 하며, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 이 개념의 가장 기초인 문제가 되겠다.

---

3. 풀이

설탕(N)이 5로 나눠질 때까지 '3kg 봉지를 추가하고 설탕에서 3kg를 빼는 작업'을 반복하면 된다. 이 작업을 반복하다가 설탕이 0 아래로 내려갔다면 이는 5kg, 3kg 봉지로는 주어진 설탕을 분배할 수 없다는 의미이므로 -1을 출력한다.