[백준/python] 2839번 설탕 배달

문제 요약

3kg과 5kg 설탕으로 최소 봉지를 사용하여 nkg을 만드는 방법

---

입력

만들어야할 설탕 kg N (3 ≤ N ≤ 5000)

---

출력

봉지의 최소 개수, 만들 수 없다면 -1

---

코드 

 

입력을 받고 입력의 범위에 따라 dp의 크기를 선언한다. dp=[-1]*n으로 할 시에는 n=1일 경우 5,6,7에 미리 정의해둔 값들이 인덱스 밖의 값이 되므로 주의해야한다.

이 문제는 다이나믹 프로그래밍으로 푸는 문제이다.

큰 문제를 작은 문제로 쪼개는 다이나믹 프로그래밍의 형태처럼 dp[i-3], dp[i-5]의 값을 참고하여 dp[i]의 값을 정의한다. dp[i]의 값이 궁금할때 dp[0]~dp[i-1]까지의 값은 모두 최소값으로 이미 정의되어있으므로 이를 쉽게 참고할 수 있다!

따라서 첫번째 if 문에서는 dp[i-3]의 값을 참고하여 정의하는 경우, 두번째 if문의 첫번째 if문에서는 dp[i-5]의 값을 참고하여 정의하는 경우, 두번째 if문의 두번째 if문에서는 dp[i-3], dp[i-5] 중 작은 값을 골라서 참고하여 정의하는 경우로 조건을 나눌 수 있다.

---

이 문제는 쉬운편이지만 다이나믹 프로그래밍을 처음 해볼때는 접하기 좋은 문제인 것 같다