백준 11052번 [카드 구매하기](C++) -yes6686- 티스토리

백준 문제 풀이: 11052 [카드 구매하기]

---

문제 링크: https://www.acmicpc.net/problem/11052

문제 설명:

1부터 N까지의 카드 묶음을 살 수 있으며, 각 카드 묶음의 가격이 주어질 때, 정확히 N개의 카드를 구매하는 데 지불해야 하는 최대 비용을 구하는 문제입니다.

즉, 카드 묶음을 어떻게 조합하느냐에 따라 최대 비용을 얻도록 해야 합니다.

---

문제 해결 코드

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

int arr[1001]; // 카드 묶음의 가격을 저장하는 배열
int dp[1001];  // N개의 카드를 구매하는 데 지불해야 하는 최대 비용

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 구매할 카드의 수
    cin >> n;

    // 카드 묶음 가격 입력
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    // 동적 프로그래밍 계산
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], dp[i - j] + arr[j]);
        }
    }

    // 결과 출력
    cout << dp[n] << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여, N개의 카드를 구매하기 위해 선택 가능한 모든 카드 묶음의 조합을 시도하며 최대 비용을 계산합니다.
• 구현 세부사항:
  • dp[i]: 정확히 i개의 카드를 구매하기 위한 최대 비용을 저장합니다.
  • 점화식: dp[i] = max(dp[i], dp[i - j] + arr[j])
  • 각 묶음의 크기를 반복하며 최적의 조합을 찾습니다.
• 시간 복잡도 분석: O(n²)
  • 이중 반복문을 사용하며, n개의 카드에 대해 모든 가능한 조합을 확인합니다.

---

결과

N개의 카드를 구매하기 위한 최대 비용을 정확히 계산합니다. 각 카드 묶음을 반복적으로 비교하여 최적의 조합을 찾습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!