[백준][Python] 1823 수확

각 value, cnt를 축으로 둔 2차원 dp를 통해 하나씩 고르는 경우의 수를 check해주었습니다.

이전에 수확한게 왼쪽인지 오른쪽인지 각각 수확량의 최댓값을 취하며 계산해 주었습니다.

 

import sys
input = sys.stdin.readline

N = int(input())
v = [0]+[int(input()) for _ in range(N)]
dp = [[v[i] * N  if i == j else 0 for i in range(N + 1)] for j in range(N + 1)]

for left in range(1, N + 1):
    for right in range(left - 1, 0, -1):
        dp[right][left] = max(dp[right + 1][left] + v[right] * (N - left + right), dp[right][left - 1] + v[left]*(N - left + right))

print(dp[1][N])