# 백준 : 설탕 배달(2839)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2839_sugardelivery)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;

#define MAX 5000

int sugarkg[MAX + 1];
int dp[MAX + 1];
int basket[2] = {3, 5};

int main(void)
{
    int total;
    cin>>total;
    
    dp[0] = 0;
    dp[1] = MAX;
    dp[2] = MAX;
    
    // calculation
    for(int i=3; i<=total; i++) {
        dp[i] = MAX;
        for(int j=0; j<2; j++) {
            if(i >= basket[j]) {
                dp[i] = min(dp[i], dp[i - basket[j]] + 1);
            }
        }
    }
    if(dp[total] >= MAX)    cout<<"-1"<<endl;
    else                    cout<<dp[total]<<endl;
    return 0;
}

풀이

이제 DP 문제를 보면 어떻게 풀어야하는지 좀 알 것 같다.
이번 문제는 kg도 이미 예시로 들어놓았고, 만들 수 없는 경우에 -1만 제대로 출력해주면 된다.
나는 최대 값보다 큰 경우(min으로 만들어지지 못하는 경우)에만 -1로 출력해주도록 하였다.
0은 어차피 시작점이 될 수 있으니까 제외한다.