boj.kr/11052 카드 구매하기 (silver1) 파이썬 풀이

1. dp 배열을 N+1 * N+1 의 크기로 초기화한다.

2. dp[1][x] 값을 cards[1] * x 값으로 초기화한다.

3. dp[ci][ni] 값을 카드를 ci번째까지 검사했을 때 총 ni 개의 카드를 갖는 최대 가격으로 저장한다.

3.1. 이전 검사에서 ni개의 카드를 갖는 최대 가격 -> dp[ci-1][ni] 

3.2 이전 검사에서 ni-ci개의 카드를 갖는 최대가격 + ci개에 해당하는 카드 가격 -> dp[ci-1][ni-ci] + cards[ci] 

3.3. 현재 검사에서 ni-ci개의 카드를 갖는 최대가격 + ci개에 해당하는 카드 가격 -> dp[ci][ni-ci]+cards[ci] 를 비교하고

3.4. 현재 검사에서 ni-(1이상ni미만)개의 카드를 제외하는 경우의 최대 가격 + (1이상ni미만)개에 해당하는 카드 가격 -> dp[ci][ni-(1이상ni미만)]+cards[1이상ni미만] 값과 차례대로 비교해 최대값을 저장한다.

4. dp에서 최대값을 출력한다.

 

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

for ci in range(2, len(cards)):
    for ni in range(ci, N+1):
        dp[ci][ni] = max(max(dp[ci-1][ni]
                        , dp[ci-1][ni-ci] + cards[ci])
                        , dp[ci][ni-ci]+cards[ci])
        for _ in range(1, ni+1):
            dp[ci][ni] = max(dp[ci][ni], dp[ci][ni-_]+cards[_])
ans = -1e9
for y in range(len(dp)):
    for x in range(len(dp[y])):
        ans = max(ans, dp[y][x])

print(ans)

 

dp[ci][ni] 값을 카드를 ci번째까지 검사했을 때 총 ni 개의 카드를 갖는 최대 가격으로 저장할 수 있다.

* Python3으로 제출하는 경우 시간초과가 발생하고 PyPy3으로 제출해야 통과한다.