백준 SILVER 1 [11052번] 카드 구매하기 {언어 : Python}

문제 링크

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

정답 코드

import sys

# 입력
input = sys.stdin.readline
n = int(input())
cards = [0] + list(map(int, input().split())) # 계산이 쉽게 0번 인덱스 추가

# 탐색
dp = [0 for _ in range(n+1)]
dp[1] = cards[1]
for i in range(2, n+1):
    for j in range(1, i):
        dp[i] = max(dp[i-j]+dp[j], dp[i])
    dp[i] = max(dp[i], cards[i])
print(dp[n])

풀이 방법

1. dp 계산이 쉽게 0번 인덱스를 추가해준다.
   • 이렇게 하면 1개 일 때 cards[1] 이렇게 계산할 수 있다.
2. 각 구간에서 최대로 돈을 낼 수 있는 방법을 찾는다.
   • dp의 1번 인덱스는 1개를 구매할 때 돈을 최대한 내는 방법이다.
   • 즉, dp의 n번 인덱스는 n개를 구매할 때 돈을 최대한 지불하는 방법을 저장하는 메모이제이션을 사용했다고 볼 수 있다.
   • 저장하는 방식은 다음과 같다.
     1. j인덱스로 dp에 저장된 값들로 최대값을 갱신한다.
        1. 예를 들어 5번 인덱스라면 dp[4] + dp[1], dp[3] + dp[2] 중에서 최대 값을 넣어준다.
        2. 이후 순수 cards[5]와도 비교하면서 최대 값을 갱신한다.
        3. dp[5] = max(dp[4] + dp[1], dp[3] + dp[2], cards[5])
        4. 밑에 표를 보면 더 이해하기 쉽다.
3. 계산이 끝나면 dp[n]은 자연스럽게 가장 큰 값이 저장된다.

• n=4
• cards = [5, 2, 8, 10]

n개 일 때 최대 값	dp[1]	dp[2]	dp[3]	dp[4]	dp[n]
계산 식	cards[1]	max( cards[2], dp[1] + dp[1] )	max( cards[3], dp[2]+dp[1] )	max( cards[4], dp[3]+dp[1], dp[2]+dp[2] )	max( cards[n], dp[n-1]+dp[1], dp[n-2]+dp[2], ..., dp[1]+dp[n-1] )
값	5	10	15	20

느낀점

• 다시 보면 좋을 것 같은 문제다.
• dp가 1 ~ n까지만 생각할 수 있는데 n의 범위가 1000이라면 n ** 2도 가능하다고 생각하면 좋다.
• 만약 n번만 반복해도 계산이 가능하다면 아직 갈 길이 멀구나 싶다.