Algorithm

[C++] 백준 4781 사탕 가게 - Unbounded Knapsack (DP)

Rubi ❤️ 2025. 3. 21. 00:08
728x90
반응형

백준 4782번 사탕 가게 문제는 정해진 예산 안에서 최대 칼로리를 얻는 방법을 찾는 문제로,
Unbounded Kapsack (중복 구매 가능) 유형의 전형적인 DP 문제 입니다.

🔍 문제 요약

문제 링크: 백준 4781번 사탕가게

 

  • 목표: 총 예산 T센트를 초과하지 않으면서 최대한 많은 칼로리의 사탕 구매
  • 조건:
    • 사탕 개수 N (1 <= N <= 5,000)
    • 사탕 가격 P , 사탕 칼로리 C
    • 사탕은 중복 구매 가능하다
  • 제한:
    • T <= 10,000 센트 -> 100.00 달러에서 센트로 정수 전환 필요
  • 출력:
    • 최대로 얻을 수 있는 칼로리 값

1. 💡 문제 분석

  • 무제한 중복 구매 가능 -> Unbounded Knapsack 문제
  • 가격이 float(달러)로 주어짐 -> int(센트)처리
  • 같은 사탕을 여러 번 살 수 있음.

2. 🔑 아이디어 도출

  • 가격 단위를 센트 단위로 정수 변환
  • DP 배열 사용
    • dp[i] = i 센트로 얻을 수 있는 최대 칼로리
  • 점화식
    • dp[i] = max(dp[i], dp[i - price[j] + cal[j])
    • 작은 예산부터 순서대로 채워서 중복 구매 효과 반영
현재 i센트 → 사탕 가격 K센트(price[j]) 사용 → 남는 돈 = i - K
이 때 얻는 칼로리 = dp[i - K] + 사탕 칼로리 = 남는 돈에 대한 칼로리 + 현재 구매한 사탕 칼로리
dp[i] = max(dp[i], dp[i - K] + 사탕 칼로리) 

3. 🧩 풀이 전략

  1. dp[T + 1 개] 배열 초기화
  2. 각 사탕에 대한 가격, 칼로리 저장
    • price[5001], calories[5001]
  3. 모든 예산 i에 대해 사탕을 반복 사용 가능하도록 DP 수행
  4. 최종 dp[T] 값 출력
  • 핵심 풀이
    for (int i = 0; i <= total; ++i) {          // 예산 i 센트를 기준으로
        for (auto& candy : candies) {           // 모든 사탕을 반복해서
               if (i >= candy.first) {             // i보다 가격이 작거나 같은 경우
                   dp[i] = max(dp[i], dp[i - candy.first] + candy.second);
               }
        }
    }
  • 예산이 i 센트일 때
    • 각 사탕을 한 번씩 시도하면서
      → 해당 사탕 가격만큼 뺀 dp[i - price]에 사탕의 칼로리를 더해서
      → dp[i] 갱신
    • 사탕을 반복해서 넣은 경우까지 포함됨

📦 예제 입력 & 출력

  • input
2 8.00 
700 7.00 
199 2.00 
3 8.00 
700 7.00 
299 3.00 
499 5.00 
0 0.00

 

  • output
796
798

 

4. ✅ 검증 및 테스트

  • 시간 복잡도:
    • DP
    • O(N*T) = 5,000 * 10,000 = 50,000,000 -> 1초 이내
  • 공간 복잡도:
    • dp[10001] -> 약 40KB

🖥️ 코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[10001];
int price[5001];
int cal[5001];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    while (1) {
        int n;
        double m;
        cin >> n >> m;
        if (n == 0 && m == 0.00)
            break;
        int m_cents = (int)(m * 100 + 0.5);

        memset(dp, 0, sizeof(dp));

        for (int i = 0; i < n; i++) {
            double p;
            cin >> cal[i] >> p;
            price[i] = (int)(p * 100 + 0.5);
        }

        for (int i = 0; i < n; i++) { //사탕 종류
            for (int j = price[i]; j <= m_cents; j++) {
                dp[j] = max(dp[j], dp[j - price[i]] + cal[i]);
            }
        }
        cout << dp[m_cents] << "\n";
    }
    return 0;
}

✨ 결론

  • Unbounded Knapsack의 전형적인 DP 문제
  • DP로 시간 초과 없이 해결 할 수 있다!
728x90
728x90
반응형