BOJ 11052번 카드 구매하기

BOJ : https://www.acmicpc.net/problem/11052

GitHub : https://github.com/junho0956/Algorithm/blob/master/11052/11052/%EC%86%8C%EC%8A%A4.cpp

 

아직도 solved.ac 에 의하면 실버수준인데도 DP는 진짜 갈길이 막막하다

진짜 점화식 찾는게 너무어렵다.. 진짜 이제 이정도 수준인데 숨이 막히고 포기하고 싶어진다 ㅠ

 

점화식을 간단히 설명해보자면

N개중 i개를 구매하는 시점, j번째 카드를 구매하는 시점일때

dp[i] 는 i개를 구매할 때 최댓값이고

dp[i-j]는 i개 중에서 j번째 카드를 구매하지 않은 경우 최대값이 된다. card[j]는 j번째 카드의 가격이 되겠고

결국 j번째 카드를 살지 말지를 표현하여 주면 점화식이 완성된다.

 

dp[i] = max(dp[i], dp[i-j]+card[j]) ..

 

너무 어려워서 눈물날꺼같다..

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[1001];
int card[1001];
 
int main() {
    ios::sync_with_stdio(false);
 
    int N; cin >> N;
 
    for (int i = 1; i <= N; i++) cin >> card[i];
    dp[1] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], dp[i - j] + card[j]);
        }
    }
 
    cout << dp[N];
    return 0;
}