[백준] 11052: 카드 구매하기 (Python)

문제📖

풀이🙏

-카드 N개를 갖기 위해 지불해야하는 금액의 최댓값을 출력하기 위해 dp테이블을 정의한다.

• dp[0] = 0 이고 dp[1] = data[0]의 이유는 첫번째 카드를 선택하기 때문에 초기값을 설정한다.
• 이후 카드 2개를 갖기 위해 지불해야하는 금액의 최댓값을 구하는 식은
  dp[2] = dp[1] + data[0] or dp[0] + data[1] 이고
• 카드 3개를 갖기 위해 지불해야하는 금액의 최댓값은
  # dp[3] = dp[2] + data[0] or dp[1] + data[1] or d[0] + data[2] 이므로

if dp[i] < dp[i - j] + data[j-1]:
            dp[i] = dp[i - j] + data[j-1]

다음과 같은 점화식을 이용하여 구할 수 있다.

코드💻

n = int(input())
data = list(map(int, input().split()))

dp = [0] * (n+1)
dp[0] = 0
dp[1] = data[0]

# dp[2] = dp[1] + data[0] or dp[0] + data[1]
# dp[3] = dp[2] + data[0] or dp[1] + data[1] or d[0] + data[2]
# dp[4] = dp[3] + data[0] or dp[2] + data[1] or dp[1] + data[2] + dp[0] + dp[3]
for i in range(2, n+1):
    for j in range(1, i + 1):
        if dp[i] < dp[i - j] + data[j-1]:
            dp[i] = dp[i - j] + data[j-1]
print(dp[n])