백준_2839 : 설탕 배달 - C++

문제

 

---

문제 해석

- 숫자 3과 5를 최소한으로 사용하여 더해 주어지는 수 N 을 만들어 주면 되는 문제이다.

---

알고리즘

- DP 알고리즘을 사용하면 간단하게 해결 할 수 있다.

- 우선 무게가 3, 5인 경우에는 각 3kg, 5kg 봉지 하나씩 을 사용 하면 된다.

  - 이 경우 DP[3] -> 1, DP[5] -> 1 가 되게 된다.

- 여기서 부터 시작 하여 무게가 i 일 경우에 DP[i-3] 이 만들 수 있다면 DP[i] = DP[i-3] +1이 된다.

  - 그 이유는 DP[i-3] 에서 3kg 하나만 추가 하면되기 때문이다.

- 만약 DP[i-5] 가 존재 할 때는 같은 원리로 DP[i] = DP[i-5]+1 이 된다.

- 이때 주의 해야 할 점은 i 가 '8' 같은 경우이다.

  - 이 경우에는 '8 - 3 == 5', '8 - 5 == 3' 이기 때문에 DP[i-3]과 DP[i-5] 가 동시에 존재한다.

  - 이럴 때는 두가지중 더 봉지를 적게 쓰는 경우를 대입 해 주면 된다.

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

---

코드

- 이 코드 같은 경우는 if(dp[i-3] != 0) 에서 dp[i] 에 dp[i-3] +1을 대입 했기 때문에 dp[i] = min(dp[i], dp[i-5] + 1); 로 함

#include <iostream>
using namespace std;

int dp[5001];
int N;

int main(){
    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] = min(dp[i], dp[i-5] + 1);
            } else {
                dp[i] = dp[i-5] + 1;
            }
        }
    }
    if(dp[N] == 0){
        cout << -1 << '\n';
    } else {
        cout << dp[N] << '\n';
    }
}