[Python/파이썬] 백준 1823번 수확

1823번: 수확

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
v = [0]+[int(input()) for _ in range(n)]

dp = [[0]*(n+1) for _ in range(n+1)]


def recursion(l, r, cnt):
    if l > r:
        return 0
    if dp[l][r] != 0:
        return dp[l][r]
    dp[l][r] = max(v[l]*cnt+recursion(l+1, r, cnt+1),
                   v[r]*cnt+recursion(l, r-1, cnt+1))
    return dp[l][r]


print(recursion(1, n, 1))

 

recursion 함수는 l번째~r번째 벼까지 남아있을 때의 최댓값을 리턴하는 함수이다.

• l, r은 각각 벼의 배열의 왼쪽 끝과 오른쪽 끝이고 cnt는 이번에 수확하는 벼의 순번이다.
• dp[l][r]에는 현재 상태에서 왼쪽에서 벼를 수확했을때와 오른쪽에서 벼를 수확했을때의 이익 중 큰 값을 저장한다.
• l > r인 경우는 존재할 수 없으므로 이렇게 되면 0을 리턴한다.
• dp[l][r]의 값이 이미 구해진 경우, 즉 dp[l][r] != 0인 경우에는 다시 재귀함수를 호출하여 구하더라도 값이 바뀌지는 않는다. 그러므로 dp[l][r]의 값을 그대로 리턴하면 된다.

 

재귀 함수로 DP 구현하는건 거의 안해봐서 어려웠는데 다음에 DP 문제가 나왔을 때 재귀로 구현할 수 있으면 해봐야겠다.