[백준] 11052번 카드 구매하기 (C++) - dynamic programming

문제

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

11052번: 카드 구매하기

코드

#include <iostream>

using namespace std;

int main(){
  int n;
  int dp[10001] = {0,};
  cin >> n;
  for(int i=1; i<=n; i++){
    int a;
    cin >> a;
    int max = a;
    for(int j=1; j<=i/2; j++){
      if(max < dp[j]+dp[i-j]){
        max = dp[j]+dp[i-j];
      }
    }
    dp[i] = max;
  }
  cout << dp[n];
  return 0;
}

정리

이전 dp값을 가지고 최댓값을 갱신하면서 해당 dp값을 찾으면 되는 문제이다.

참조

https://kdongree.tistory.com/46