[백준 / BOJ] 2839번 설탕 배달 (C++, Python)

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

2839번: 설탕 배달

---

문제

---

문제 풀이

수학 문제다. 푸는 방법은 DP와 그리디, 두 가지 방법이 있다.

우선 그리디로 푸는 방법은 간단하다. 최대한 적은 봉지를 들고 가고 싶다 했으니, 5kg짜리 봉지로만 담으면 된다.

처음에 주어진 N값이 5로 나누어 떨어진다면 (N % 5 == 0) 바로 5로 나눈 값을 출력하면 되고, 그렇지 않다면 3kg 봉지로 담고 출력할 값을 늘려줌과 동시에 N에서 3을 빼는 식으로 풀었다.

DP로 푸는 방법도 코드 길이만 보면 간단하다. 우선 dp[3], [5]를 1로 초기화해준다. (기본값이기 때문에)

현재 ikg의 최소 봉지수를 구하려면, 이전에 계산한 (i - 3)kg과 (i -5)kg의 최솟값을 비교하면 될 것이다. 비교한 최솟값에 +1을 한 값을 dp[i]에 넣고, 만약 이 값이 최댓값 5000보다 크다면 -1을 출력하도록 했다.

 

 

C++ 코드 전문

 

Python 코드 전문

 

소감