카드 구매하기 백준 11052

문제

카드 구매하기 백준 11052번

리뷰

유념해야 할 것은 카드 i개 들어있는 카드팩 가격이 P[i] 원 이라는 것이다.

점화식을 세우는 게 쉽지 않았다.

입력받은 카드팩 가격 배열 P[i]와 i장 샀을 때 최대값을 기억하는 배열 M[i]를 사용한다.

예제 입력 n = 4 , P[i] = [1, 5, 6, 7] 일 때, 예제 출력은 10이다.

카드 a 장을 살 때 최대 지불하는 금액을 배열 M[a] 에 넣고, 최종 답 M[n]을 구한다.

M[1] = max(P[1], M[1])

M[2] = max(M[1] + P[1] , M[2])

i = 5 인 경우,

M[1] + P[4], M[2] + P[3], M[3] + P[2] , M[4]+P[1] 인 경우를 비교해야 한다. -> 2중 for문

코드

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

// 카드 구매하기  (BOJ 11052) 

vector<int> P(10001);
int max_value[1001];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, num = 0;
    int i = 0, j = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++){
        scanf("%d", &num);
        P[i] = num;
    } // 카드팩 n개의 값을 입력받는다. 

    for(i = 1; i <= n; i++){

        for(j = 1; j <= i; j++){ //   

            max_value[i] = max(max_value[i-j] + P[j], max_value[i]);

        }
    }

    printf("%d", max_value[n]);

    return 0;
}