[백준] 2839: 설탕 배달

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

2839번: 설탕 배달

코딩테스트 대비를 위해 자주 출제되는 유형 Dynamic Programming을 풀어본 지 오래돼서 천천히 브론즈 문제부터 풀기 시작했다.

쉬운 DP 문제였기에 1차원 배열으로 풀면 된다. 이 문제에서 요구하는 봉지의 수를 기준으로 배열을 설정한다.

여기서 주의해야하는 점은 그냥 DP 점화식을 입력하면 예상과 다르게 작동한다. 왜냐하면 만약 m개의 봉지 수로 n kg으로 정확히 맞춰서 들고 갈 수 없는 경우에는 dp[n] = 0으로 처리되기 때문에 min함수를 거치면 반드시 선택 대상이 되기 때문이다.

그래서 dp[n]이 0일 때는 별도의 처리가 필요하다.

#include <iostream>
using namespace std;
int dp[5001] = {0};
int main(void) {
    int n;
    cin >> n;
    dp[3] = 1;
    dp[5] = 1;
    for(int i = 6;i <= n; i++){
        if(!dp[i - 3] && !dp[i - 5]){
            dp[i] = 0;
        }
        else if(!dp[i - 3]) {
            dp[i] = dp[i - 5] + 1;
        }
        else if(!dp[i - 5]) {
            dp[i] = dp[i - 3] + 1;
        }
        else {
            dp[i] = min(dp[i - 3] + 1, dp[i - 5] + 1);
        }
    }
    if(!dp[n])
        cout << -1 << endl;
    else
        cout << dp[n] << endl;
}