문제링크

---

아이디어

다이나믹 프로그래밍 기법을 이용하면 쉽게 풀리는 문제이다.
밑에서 dp[3] = dp[5] = 1;을 해주는 이유는 3kg일때 3kg봉지 하나, 5kg일때 5kg 봉지 하나가 필요하기 때문이다. dp[0~2], dp[4]는 3kg, 5kg 봉지로 담을 수 없기 때문에 0으로 설정했다.

6kg 설탕이 있을때 3, 5kg 봉지로 얼마를 담을 수 있을지 n까지 숫자를 올리면서 기록한다.
이해를 쉽게 하기 위해 3kg 봉지 하나만 있다고 가정하자. (그러면 if(dp[i-5]) 부분이 삭제)
if(dp[3])
dp[6] = dp[3] + 1;

if(dp[4])
dp[7] = dp[4] + 1;

if(dp[5])
dp[8] = dp[5] + 1;

if(dp[6])
dp[9] = dp[6] + 1;

dp[6], dp[9]일때는 각각 설탕이 6kg, 9kg있을때이며 3kg일때 필요했던 봉지 수에 1을 더하면서 기록하는 것을 볼 수 있다.

if(dp[i-5])에서 min을 해주는데,
i가 15일때 12kg일때 필요한 3kg 봉지 수와 10kg일때 필요한 5kg 봉지 수 중에서 작은 수를 구하기 위한 것이다.

---

코드

소스코드 출처

#include <iostream>

using namespace std;

int dp[5001]; 

int main() {
	int n;
	cin >> n;

	dp[3] = dp[5] = 1;

	for (int i = 6; i <= n; i++) {
		if (dp[i - 3]) 
			dp[i] = dp[i - 3] + 1;

		if (dp[i - 5]) 
			dp[i] = dp[i] ? min(dp[i], dp[i - 5] + 1) : dp[i - 5] + 1;
	}
	cout << (dp[n] == 0 ? -1 : dp[n]) << endl;

	return 0;
}