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

개요

• 대부분 풀이는 모두 DP 1차원 배열을 활용했습니다.
• 이 문제는 DP 2차원 배열을 통해서도 풀 수 있습니다.

 

로직

• DP 테이블의 각 값은 i번까지의 카드를 조합해서 만들 수 있는 j개 카드 값들 중 최댓값
• DP 테이블의 값을 채우는 과정에서 기존 최댓값에서 현재 카드를 추가할 수 있는 경우, 현재 카드를 추가한 경우와 기존 최댓값 사이의 대소 비교를 통해 최댓값이 결정됨을 확인할 수 있음

 

소스 코드

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

int DP[1001][1001];
int P[1001];

int main() {

    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i];
    }

    /*
    1 5 6 7
    i   j
        1    2    3    4 개의 카드로 pn까지 활용해서 만들 수 있는 최대값
    p1  1    2    3    4
    p2  1    5    6    10
    p3  1    5    6    10
    p4  1    5    6    10

    점화식
    차 0이만 -> 위의 것 그대로
    차 0이상 -> 뺀 상태에서 pn 값을 더한것과 위의 값 비교, 최댓값

    if(j-i>= 0)
        DP[i][j] = max(DP[i][j-i] + P[i], DP[i-1][j])
    else
        DP[i][j] = DP[i-1][j];

    */

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (j-i >= 0) {
                DP[i][j] = max(DP[i][j-i] + P[i], DP[i - 1][j]);
            }
            else {
                DP[i][j] = DP[i - 1][j];
            }
        }
    }

    cout << DP[N][N];

    return 0;
}

 

관련 링크

11052번: 카드 구매하기