[백준] 설탕 배달 (C++)

문제

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

 

풀이

이 문제는 상근이가 3kg와 5kg 봉지를 사용하여 정확히 N kg의 설탕을 배달할 때, 최소한의 봉지 개수를 구하는 프로그램을 작성하는 문제다.

 

다이나믹 프로그래밍을 이용하여 풀이하였다.

 

dp[3] = dp[5] = 1

dp[n] = min (dp[i], dp[n - 5] + 1 )

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

int dp[5001] = { 0, };
int main() {
    int n;

    cin >> n;

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

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

        if (dp[i - 5] != 0) {
            if (dp[i] == 0) {
                dp[i] = dp[i - 5] + 1;
            }
            else {
                dp[i] = min(dp[i], dp[i - 5] + 1);
            }
        }
    }

    cout << (dp[n] == 0 ? -1 : dp[n]);
    return 0;
}