[백준(BOJ)] 11052번: 카드 구매하기 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• 주어진 예제에서 카드 1장, 2장, ... , N장을 선택할 때 가질 수 있는 가장 큰 금액을 구해서 일반화된 식을 만들었다.
• DP[i]: 카드가 i장일 때, 지불할 수 있는 가장 큰 금액
• N = 4, P = {1, 5, 6, 7} 이라고 하자.
• DP[1]은 카드 1장을 선택했을 때 지불 가능한 가장 큰 금액으로, 1장일 때 금액 1원이 최대 금액이다. DP[1] = 1
• DP[2]는 카드 2장을 선택했을 때 가장 큰 지불 금액으로, 1장*2, 또는 2장짜리를 살 수 있다. 2와 5 둘 중에서 5가 더 크므로 DP[2] = 5 (DP[i]를 가져감)
• DP[3]은 3장 짜리 선택(6), 또는 2장짜리 + 1장짜리(6), 1장짜리와 2장짜리(6) 중이므로 DP[3] =6
• DP[4]의 경우, DP[4-1]+A[1] (3장짜리+1장=7), DP[4-2]+A[2](2장짜리+2장짜리=10), DP[4-3]+A[3](1장짜리+3장짜리=7), DP[4-4]+A[4](4장짜리 1개=7) 중에서 이므로 DP[4] = 10이다.
• N = 4일 때, 지불할 수 있는 가장 큰 금액을 구하는 것이므로, DP[4]인 10이 답이 된다.

 

DP[i] = max(DP[i], DP[i-j]+A[j])

따라서 점화식은 위와 같이 되며, 초기에 모든 DP[i]=0이고, j에 대한 반복문이 돌면서 DP[i]를 가지게 되는데, 기준의 DP[i]와 j일 때 구하는 DP[i-j]+A[j] 중에서 더 큰 값을 DP[i]로 가져간다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);
    deque<int> P(N+1,0);
    deque<int> DP(N+1,0);

    for(int i=1; i<=N; i++) scanf("%d", &P[i]);
    
    for(int i=1; i<=N; i++){
        for(int j=1; j<=i; j++){
            DP[i] = max(DP[i], DP[i-j]+P[j]); //초기 DP[i]=0
        }
    }
    printf("%d", DP[N]);    
}

 

 

👏 결과

---