BOJ 11052 카드 구매하기

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

 

- DP

- 입력으로 주어진 가격을 저장하는 배열 a[]

- d[] : 구해야 할 것

- 이중 for문을 이용해야 해서 헷갈렸다.

 : d[i]를 구할때마다 1~i까지 중 최댓값을 계속 비교해야한다

 

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

int a[1010]; //주어진 것
int d[1010]; //구할 것

int main(){
  int n;
  scanf("%d", &n);
  for(int i=1; i<=n; i++){
      scanf("%d", &a[i]);
  }
  d[0]=0;
  for(int i=1; i<=n; i++){ // 1부터 n까지 1씩 증가
    for(int j=1; j<=i; j++){ // d[i] 채우기
      d[i] = max(d[i], d[i-j]+a[j]);
      // 전체가 i일때 마지막 사람에게 j개 팔기
    }
  }
  printf("%d", d[n]);
}