[백준/C++] 2839번: 설탕 배달 - 브루트 포스에서 DP로 나아가기

1. 문제 정보

• 문제 번호: 2839번
• 문제 이름: 설탕 배달
• 문제 요약: 설탕 Nkg을 배달해야 한다. 봉지는 3kg과 5kg 두 종류가 있다. 최대한 적은 수의 봉지를 사용하여 정확히 $N$kg을 만들 때, 봉지의 최소 개수를 구하라. 만약 정확히 만들 수 없다면 -1을 출력한다.

 

2. 접근 방법 (알고리즘)

❌ 첫 번째 시도: 브루트 포스 (Brute Force)

가장 먼저 떠오른 방법은 모든 경우의 수를 다 계산해보는 것이다.

• 로직: 3kg 봉지의 개수(i)와 5kg 봉지의 개수(j)를 0부터 최대치까지 이중 반복문으로 돌리며 3i + 5j = N인 경우를 찾는다. 그중 i+j가 최소인 값을 결과로 낸다.
• 단점: N이 커질수록 반복 횟수가 늘어나 성능이 저하된다. 

✅ 두 번째 시도: 다이내믹 프로그래밍 (DP)

문제를 작은 조각으로 쪼개서 생각하는 방식이다. "10kg을 만드는 최소 봉지 수는 7kg을 만드는 최소 수 + 1(3kg 봉지 추가) 혹은 5kg을 만드는 최소 수 + 1(5kg 봉지 추가) 중 작은 값이다"라는 논리를 세우는 것이다.

 

 

3. 핵심 개념: 다이내믹 프로그래밍(DP)이란? 🧠

DP는 "이미 구한 정답을 메모리에 저장해두고 재활용하는 방식"이다.

1. Overlapping Subproblems (겹치는 부분 문제): 큰 문제를 풀기 위해 반복되는 작은 문제들이 존재한다.
2. Optimal Substructure (최적 부분 구조): 작은 문제들의 최적의 답을 모으면 큰 문제의 최적의 답이 된다.

이 문제에서 dp[i]를 "ikg을 만드는 데 필요한 최소 봉지 수"라고 정의하면 다음과 같은 관계가 성립한다.

• dp[i] = min(dp[i-3], dp[i-5]) + 1$ (단, dp[i-3]이나 dp[i-5]가 존재할 때)

 

 

 

 

4. 코드 구현

 

💻 브루트 포스 코드 (처음 풀이)

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int result = -1, k, a = 3, b = 5;
    cin >> k;

    int limitA = k / a;
    int limitB = k / b;

    for (int i = 0; i <= limitA; i++) {
        for (int j = 0; j <= limitB; j++) {
            int check = i * a + j * b;
            if (check == k) {
                if (result == -1) result = i + j;
                else result = min(result, i + j);
            }
        }
    }
    cout << result;
}

 

 

💻 DP 코드 (개선된 풀이)

#include <iostream>
#include <algorithm>

using namespace std;

int dp[5001]; // 전역 변수: 0으로 자동 초기화

int main() {
    int n;
    cin >> n;

    // 기저 상태 정의: 3kg, 5kg은 각각 봉지 1개로 완성 가능
    dp[3] = dp[5] = 1;

    // 6kg부터 목표인 nkg까지 순차적으로 최소값을 채워나감 (Tabulation)
    for (int i = 6; i <= n; i++) {
        // 1. 3kg 봉지를 추가하는 경우
        if (dp[i - 3]) {
            dp[i] = dp[i - 3] + 1;
        }

        // 2. 5kg 봉지를 추가하는 경우
        if (dp[i - 5]) {
            // 이미 dp[i-3]에 의해 값이 채워졌다면 비교 후 최소값 선택
            // 아니면 처음 채우는 것이므로 그대로 저장
            dp[i] = dp[i] ? min(dp[i], dp[i - 5] + 1) : dp[i - 5] + 1;
        }
    }

    // 만약 dp[n]이 0이면 정확히 만들 수 없는 경우이므로 -1 출력
    cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
    return 0;
}

---

5. 배운 점 & 회고 (TIL) ✍️

① 시간 복잡도의 비약적 향상

브루트 포스 방식은 반복문이 중첩되어 연산량이 많았지만, DP 방식은 6부터 N까지 딱 한 번만 훑으면 된다. 즉, 시간 복잡도가 O(N)으로 매우 효율적이다.

② 과거의 결과가 현재를 만든다

DP의 핵심은 "내가 지금 ikg을 어떻게 만들지?"가 아니라 "내가 이미 알고 있는 i-3kg이나 i-5kg의 최적해에 봉지 하나만 더 얹으면 어떨까?"**라는 관점의 전환이다. 이를 위해 배열(dp[])에 값을 기록해두는 것이 중요하다.

 

③ 삼항 연산자와 예외 처리

수정 코드에서 사용된 dp[i] = dp[i] ? min(dp[i], dp[i-5] + 1) : dp[i-5] + 1; 구문은 상당히 유용하다.

• dp[i]가 이미 존재한다면(true) 기존 값과 비교하고,
• 0이라면(false) 5kg 봉지 연산 결과를 처음으로 저장한다.
• 이처럼 0(불가능)과 실제 값(가능)을 구분하여 예외 상황을 처리하는 연습이 더 필요하다는 점을 느꼈다.

---

다음 공부 목표:

DP에는 상향식(Tabulation, 반복문)과 하향식(Memoization, 재귀) 두 가지 방식이 있다고 한다. 이번에는 반복문을 썼으니 다음에는 재귀를 이용한 DP 문제도 풀어봐야겠다.

DP의 점화식을 세우는 과정이 아직은 낯설지만, 작은 문제부터 규칙을 찾는 연습을 꾸준히 해야겠다.

https://chae52.tistory.com/206 

DP : Dynamic Programming : 동적 계획법 : 동적 프로그래밍 : 다이나믹 프로그래밍개념 정리/template/상향

 

https://www.youtube.com/watch?v=oBt53YbR9Kk

 

---

함께 읽어보면 좋은 글:

• [C++ 배정밀도와 부동소수점 오차 정리]
• [그리디 알고리즘으로 푸는 설탕 배달] (사실 이 문제는 그리디로도 풀 수 있다!)