[Python] 백준2839 설탕 배달

28 Dec 2022 in Study on Algorithm

백준2839 설탕 배달 링크

문제

예제 입력

---

코드

suger = int(input())
count = 0

while suger >= 0:
  if suger % 5 == 0:
    count += suger // 5
    print(count)
    break
  
  suger -= 3
  count += 1
  
else:
  print(-1)

설명

파이썬을 통해서 사용자로부터 입력받아 조건문/반복문으로 사용하여 설탕 배달을 구현했습니다.

---

정리

처음 문제를 봤을 때는 거스름돈 문제와 같아 접근했는데 거스름돈이 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문입니다. 만약 큰 단위의 동전이 작은 단위의 동전의 배수가 아니면, 작은 단위의 동전을 종합해가 다른 해가 나올 수 있어 그 때는 동적계획 알고리즘으로 해결해야 합니다. 그래서 dp로 해결할려고 했지만 마땅한 점화식이 나오지 않아 규칙성이 없다는 것을 깨닳아 조건문/반복문으로 풀었습니다.

---

결과