[백준]11052 카드구매하기 16194 카드구매하기2 파이썬 python

문제링크

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

11052번: 카드 구매하기

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

16194번: 카드 구매하기 2

코드

import sys
import math
input = sys.stdin.readline
 
n = int(input())
d = list(map(int, input().split()))
 
for i in range(n):   
    for k in range(math.ceil(i/2)):
        tmp = d[k]+d[i-k-1]       
        if tmp>d[i]:
            d[i]=tmp
print(d[n-1])

import sys
import math
input = sys.stdin.readline
 
n = int(input())
d = list(map(int, input().split()))
 
for i in range(n):   
    for k in range(math.ceil(i/2)):
        tmp = d[k]+d[i-k-1]       
        if tmp<d[i]:
            d[i]=tmp
print(d[n-1])

POINT

- DP로 접근 가능 

 

- 카드구매하기 풀이방법:

n번째 할 수 있는 행동 = +1, +2, ..., +n 개 포함한 카드팩 선택하기

'd[i] = i개 카드를 구매 시 최대 비용' 이라고 정의한다.

d[n]을 구하기 위해서, 후보군 : (d[n-1] + d[1])  , (d[n-2] + d[2]) ,  (d[n-3] + d[3]) , ... , (d[n]) 값을 전부 구한 뒤,

제일 큰 값으로 d[n]을 갱신한다. 이때, d[n-1]까지 최대값이 다 저장되어있기 때문에 DP 방식으로 접근 가능한 것이다. 

 

* 코드에서는 list d의 index를 0부터 시작하여 이 점을 고려해주어야한다.

또한, d[2]+d[3] = d[3]+d[2] 이므로 i/2 까지만 for문을 돌려서 후보군을 생성해준다.

 

* 카드구매하기2 의 경우, 

'd[i] = i개 카드를 구매 시 최소 비용' 이라고 정의한다. -> 카드구매하기 코드에서 부등호만 반대로 바꿔주면 풀이 완료!