2839: 설탕배달 (DP 풀이)

[minsoo0715]

2839: 설탕 배달

소스 코드

아이디어

설탕이 Nkg일 때 최소한의 봉지의 양을 $A_N$이라고 하면
처음에 5kg 봉지로 설탕을 넣는 경우와, 3kg 봉지로 설탕을 넣는 경우로 나눌 수 있다.
5kg 봉지로 설탕을 넣기 시작할 때의 봉지의 최솟값은 결국 $A_{N-5} + 1$와 같다. 3kg의 경우도 $A_{N-3} + 1$과 같다.
즉, 이 두 경우 중에 가능한 경우에서 최솟값을 가지는 게 $A_N$이다.

따라서 다음과 같이 식을 세울 수 있다.

• $A_{N-5}$와, $A_{N-3}$이 가능한 경우
  $$A_N = min(A_{N-5}, A_{N-3}) + 1$$

• 둘다 불가능한 경우 $$A_N = -1$$

• 둘 중 하나만 불가능한 경우 $$A_N = A_{N-5} + 1\quad 또는\quad A_N = A_{N-3} + 1$$

구현

위 점화식을 반복문을 통해 down-top 방식으로 구현.

vector<int> dp = vector<int>(5001, -1); // 불가능한 경우의 값인 -1을 초깃값으로 지정

dp[3] = dp[5] = 1; // 초기 값

for(int i = 6; i<=N; ++i) {
    s5 = dp[i-5]; s3 = dp[i-3];
    if(s5 > 0 && s3 > 0) {               // 두 경우 모두 가능한 경우
        dp[i] = min(s3, s5) + 1;
    }else if(s5 < 0 && s3 < 0) {         // 두 경우 모두 불가능한 경우
        dp[i] = -1;
    } else {                             // 두 경우 중 하나만 가능한 경우
        dp[i] = (s3 > 0 ? s3 : s5) + 1;  // 가능한 경우의 수 + 1
    }
}
    cout << dp[N];
    return 0;