[C++] 백준 2839번 설탕 배달

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;
}