(백준 알고리즘 문제풀이) 11052번 카드 구매하기

문제

문제 링크

 

문제 접근

• dp를 활용하는게 효율적인 코드를 만들 것 같다.
• 개수에 따라서 최대 값을 dp에 저장시킴으로써 정답을 도출할 수 있을 것으로 예상했다.

코드

import sys

N = int(sys.stdin.readline())

P = list(map(int, sys.stdin.readline().split()))

dp = list([0] * (N + 1))

for i in range(1, N+1):
    for j in range(1, i+1):
        dp[i] = max(dp[i], dp[i-j] + P[j-1])

print(dp[len(dp)-1])

느낀점

파이썬에서 dp를 이용하기 위해서 list의 개수를 두번째 for 를 이용하기 위해서 N + 1개로 만들어주어야 하는 것을 깨닫게 되었다. 문제를 풀다가 자꾸 10개의 카드를 고르는 가격에 대하여 결과값이 도출이 되어야 하는데 10번째 loop가 돌지 않았기 때문에 9개의 카드를 골랐을 경우의 가격에 대한 결과값이 도출이 된 것이었다. dp를 이용할 때에는 루프의 성질을 잘 이해한 후 해결하는 능력을 키워나가야하겠다 다짐하게 되었다.