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

 

1. 문제

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

2839번: 설탕 배달

 

2. 문제 접근

입력 받은 N 값을 어떻게 하면 최대한 적은 봉지로 나눌 수 있는지 생각해야 한다.

초기에는 N값을 받고 5로 나누고, 5로 나눈 나머지 값을 다시 3으로 나눈 나머지가 0이면, (5로 나눈 몫 + 3으로 나눈 몫) 으로 결과값을 내려고 했다. 그러나, 이런 방식은 오래 걸리고 복잡하다.

 

그래서 결론적으로 시도했던 방법은, Dynamic Programming을 이용했다.

DP[] 배열을 생성하고 DP[i]에 ikg이 되려면 필요한 봉지 수를 저장한다. 따라서, 현재 i kg를 달성하려면 전에 계산한 (i-3)kg와 (i-5)kg 중 작은 것에 1을 더하면 현재 i kg을 채울 수 있는 최소의 봉지수가 나온다. 그래서 아래와 같은 수식으로 계산할 수 있다.

 

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

 

3kg, 5kg일 때 최소의 봉지수는 1개이므로, dp[3] = dp[5] = 1이다. 예를 들어 4 같은 경우는 3과 5로 표현할 수 없는 수이기 때문에 0으로 저장한다. 따라서 0이 최솟값으로 하고, dp[i-3] 또는 dp[i-5]이 0 이상의 값일 때만 계산하게 하는 것이다.

 

그리고 6kg 이후부터 위의 수식으로 값을 저장한다. dp[6]을 계산하면, min(dp[3] + 1, dp[1] + 1) = 2이다.

 

 

3. 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> dp(n+1, 0);

    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-5]+1;
    }
    cout << (dp[n] == 0 ? -1 : dp[n]);
}