[백준/Python] 11052번(DP)_카드 구매하기

📌문제 유형

DP (실버1)

 

📌문제

11052번: 카드 구매하기

 

📌나의 문제풀이

- dp[2]부터 dp[n]까지 최댓값 갱신

- j == k-j 까지 진행하여 최댓값 갱신 

n = int(input())
dp = [0 for _ in range(1001)]

li = list(map(int,input().split()))
for i in range(1,n+1):
    dp[i] = li.pop(0)

for k in range(2,n+1):
    for j in range(k//2+1):
        if dp[j] + dp[k-j] > dp[k]:
            dp[k] = dp[j] + dp[k-j]
print(dp[n])

 

📌 다른사람의 문제풀이

N = int(input())
p = [0] + list(map(int,input().split()))
dp = [0 for _ in range(N+1)]


for i in range(1,N+1):
    for k in range(1,i+1):
        dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[i])

 

📌 리뷰 

- DP가 필요한 N까지만 테이블 생성하기