[백준 2839] 설탕 배달

백준 2839

🔍 알고리즘 분류

• 그리디
• 다이나믹 프로그래밍

💡 문제 풀이

1. 그리디
   1) 5의 배수인지 확인 => 맞다면 5킬로 봉지만 사용하는 것이 최선
   2) 5의 배수가 아니라면 N-3 (=3킬로 봉지 사용)
   3) 위 과정 반복
2. DP
   1) N까지의 배열 생성 후 최댓값으로 초기화
   2) 3의 배수와 5의 배수일 경우 몫으로 갱신
   3) 배열 순회하며 3과 5의 조합으로 만들 수 있는 경우
   • i-3이 존재할 때 현재값과 현재값+1 (3킬로 봉지 1개 추가) 비교 후 최솟값 선택
   • i-5이 존재할 때 현재값과 현재값+1 (5킬로 봉지 1개 추가) 비교 후 최솟값 선택

📄 코드

• C++

1. 그리디 풀이

#include <iostream>
// #include <algorithm>
#include <vector>
using namespace std;

int N;
int ans = 0;

int main() {
    cin >> N;

    while (N) {
        // 5의 배수라면 5킬로 봉지만 쓰는 것이 최소 개수임
        if (N % 5 == 0) {
            ans += int(N / 5);
            break;
        }
        // 5의 배수가 아니라면 3킬로 봉지 사용
        else {
            N -= 3;
            ans++;
        }
    }

    if (N < 0) cout << -1;
    else cout << ans;
 
    return 0;
}

2. DP 풀이

#include <iostream>
#include <vector>
using namespace std;

int N;

int main() {
    cin >> N;

    // i킬로그램을 담을 수 있는 최소 봉지 수
    vector<int> arr(N + 1, N);

    // 3의 배수와 5의 배수 초기화
    for(int i = 3; i <= N; i++) {
        if (int(i % 3) == 0) {
            arr[i] = int(i / 3);
        }
        if (int(i % 5) == 0) {
            arr[i] = int(i / 5);
        }
    }

    // 8부터 시작하는 이유: 3킬로 봉지와 5킬로 봉지로 만들 수 있는 최소 수
    for(int i = 8; i <= N; i++) {
        // 3킬로 봉지 1개 추가해서 만들 수 있는 경우
        if (arr[i - 3]) {
            // 현재 값보다 작을 때에만 갱신
            arr[i] = min(arr[i], arr[i - 3] + 1);
        }
        // 5킬로 봉지 1개 추가해서 만들 수 있는 경우
        if (arr[i - 5]) {
            // 현재 값보다 작을 때에만 갱신
            arr[i] = min(arr[i], arr[i - 5] + 1);
        }
    }

    // 결과 출력
    if (arr[N] == N) cout << -1;
    else cout << arr[N];

    return 0;
}