BOJ
BOJ 11052 카드 구매하기
@떠니
2019. 7. 18. 20:27
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]);
}