백준 11052 카드구매하기

문제

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

풀이전략

1. 최대한 돈을 많이 사용하도록 풀어야한다.
2. 작은 값부터 순차대로 모든 경우의 수를 확인하여 문제를 해결한다. 단 이때 메모이제이션을 하여 시간복잡도를 낮춘다.

코드

#include<bits/stdc++.h>

using namespace std;

#define mine

vector<int> p(1001);
int dp[1001];
int main(){
    int n;
    cin >> n;

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

    for(int i=1; i<=n; i++){
    	// dp[1] 부터 순서대로 값을 계산하게 된다. 
        // dp[i-j] + p[j] 의 최대값이 곧 dp[i]의 값이 된다.
        for(int j=1; j<=i; j++){
            dp[i] = max(dp[i], dp[i-j]+p[j]);
        }
    }
    cout << dp[n];
    return 0;
}

소감

내가 해결하지 못하여 다른사람의 블로그를 참고하였다. 하지만 핵심은 하나다. 이 문제에서 N개의 카드가 주어지는데, 이러한 카드가 주어질 때 이 카드들 만으로 계산을 순차적으로 하면 된다. 이러한 테크닉을 배우게 되었다.
dp[i] = max(dp[i], dp[i-j]+p[j]) 이러한 방법을 잊지말자.