티스토리 뷰

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번째 카드 중 최댓값 구하면됩니다.

 

 

구현 코드

 

'Coding Test > 백준' 카테고리의 다른 글

[C++] 백준 2011 - 암호코드  (1) 2020.08.14
[C++] 백준 2225 - 합분해  (0) 2020.08.13
[C++] 백준 9461 - 파도반 수열  (0) 2020.08.12
[C++] 백준 2133 - 타일 채우기  (0) 2020.08.11
[C++] 백준 1699 - 제곱수의 합  (0) 2020.08.10