https://www.acmicpc.net/problem/2839
Bottom-Up 방식으로 풀었다.
dp(k)을 설탕 n킬로그램의 배달에 필요한 봉지의 최소 개수라고 정의하자.
3킬로그램 봉지의 개수를 i개, 5킬로그램 봉지의 개수를 j개라고 하면 설탕의 무게(k)는 i*3 + j*5이다.
이때, 같은 k에 대하여 여러 (i, j)쌍이 존재할 수 있으므로 매 단계에서 (i+j)의 최소값을 dp(k)에 저장한다.
그리고 k가 (i, j)의 조합으로 만들어질 수 없는 경우는 dp(k)가 초기값을 가지고 있으므로 -1을 출력한다.
#include <iostream>
using namespace std;
const int MAX = 5000;
int dp[5001];
int main()
{
int n, weight;
cin >> n;
for(int i=0; i<=n; i++) dp[i] = MAX;
for(int i=0; i*3<=n; i++){
for(int j=0; j*5<=n; j++){
weight = i*3 + j*5;
if(weight > n) break;
dp[weight] = min(dp[weight], i+j);
}
}
if(dp[n] == MAX) cout << -1;
else cout << dp[n];
return 0;
}