Coding Test/백준
[C++] 백준 11052 - 카드 구매하기
Junchoi
2020. 8. 15. 14:00
문제 링크
https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
카드 4개를 살 때의 최댓값은
1. 카드 3개를 살 때의 최댓값 + 1번째 카드
2. 카드 2개를 살 때의 최댓값 + 2번째 카드
3. 카드 1개를 살 때의 최댓값 + 3번째 카드
4. 카드 0개를 살 때의 최댓값 + 4번째 카드
위 4가지 방법 중 최댓값을 구하면 됩니다.
따라서 카드 n개를 살 때의 최댓값은
카드 n-1개를 살 때의 최댓값 + 1번째 카드
카드 n-2개를 살 때의 최댓값 + 2번째 카드
.
.
카드 0개를 살 때의 최댓값 + n번째 카드 중 최댓값 구하면됩니다.
구현 코드