[C/C++] BOJ 11052 :: 카드 구매하기

BOJ 11052 :: 카드 구매하기

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

나의 풀이

학부 고급알고리즘 시간 때 배운 Knapsack 알고리즘을 생각하며 풀었다!

1. 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값은 카드 1개가 포함된 카드팩의 가격이므로 그 값을 그대로 저장한다.

2. 카드 2개부터는 지금까지 저장한 카드를 갖기위해 지불해야 하는 금액의 최댓값과 카드팩의 가격을 이용하여 비교한 후 갱신한다.

Ex) 카드 2개를 갖기 위해 지불해야 하는 금액의 최댓값은

1) 카드 0개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카드 2개가 포함된 카드팩의 가격 = 5

현재 저장되는 최댓값은 5

2) 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카드 1개가 포함된 카드팩의 가격 = 2

비교 결과, 저장되는 값은 5

이와 같은 식으로 dp 배열을 갱신해 나가면 dp[N]에 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값이 저장된다.

예제 입력 1에서의 dp 배열의 값은 1 5 6 10 이 된다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11052/BOJ_11052.cpp

// 백준알고리즘 11052번 :: 카드 구매하기
#include<iostream>
using namespace std;
#define max(a, b) (a > b) ? a : b
 
int N;
int arr[1002];
int dp[1002];
 
int main(void)
{
    cin >> N;
 
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
    
    dp[1] = arr[1];
 
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j < i; j++) {
            dp[i] = max(dp[i], dp[j] + arr[i - j]);
        }
    }
 
    cout << dp[N];
    return 0;
}