[백준알고리즘] 11052번: 카드 구매하기 -Python

[백준알고리즘] 11052번: 카드 구매하기 -Python

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

11052번: 카드 구매하기

반드시 N개를 구매하면서 가장 비싸게 주고 사는 경우를 구해야 한다.

 

입력받은 값으로부터 누적해 나가면서 i개를 살 때 가장 비싸게 주는 값을 구해나갔다. 최종적으로 N개를 구매할 때 가장 비싸게 사는 방법을 계산했다.

 

각 인덱스 마다 값을 구하기 위해서 다음과 같이 생각했다.

1개를 살 때:

  0 + 1

2개를 살 때:

  0 + 2

  1 + 1

3개를 살 때:

  0 + 3

  1 + 2

4개를 살 때:

  0 + 4

  1 + 3

  2 + 2

 

즉, 1개를 살 땐 (0개 살 때의 최댓값 + 1개 살 때의 최댓값)을 구했다.

2개를 살 땐 (0개 살 때의 최댓값 + 2개 살 때의 최댓값)과 (1개 살 때의 최댓값 + 1개 살 때의 최댓값) 중 큰 값을 유지하도록 했다.

마찬가지로 4개를 살 땐 다음 3가지의 경우 중 가장 큰 값을 유지하려 했다.

(0개 살 떄의 최댓값 + 4개 살 때의 최댓값)

(1개 살 떄의 최댓값 + 3개 살 때의 최댓값)

(2개 살 때의 최댓값 + 2개 살 때의 최댓값)

 

이런 식으로 최댓값을 유지해 나갔따.

import sys

N = int(sys.stdin.readline())
price = [0]
price += list(map(int, sys.stdin.readline().split()))

for idx in range(1, N+1):
    tmp = []
    for t in range(idx//2 + 1):
        tmp.append(price[t] + price[idx-t])
    price[idx] = max(tmp)

sys.stdout.write(str(price[N]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다