1823번: 수확
첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다.
www.acmicpc.net
코드
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 문제가 나왔을 때 재귀로 구현할 수 있으면 해봐야겠다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 1757번 달려달려 (0) | 2024.04.09 |
---|---|
[Python/파이썬] 백준 2670번 연속부분최대곱 (0) | 2024.04.04 |
[Python/파이썬] 백준 4095번 최대 정사각형 (0) | 2024.02.10 |
[Python/파이썬] 백준 17484번 진우의 달 여행 (Small) (0) | 2024.02.04 |
[Python/파이썬] 백준 13302번 리조트 (0) | 2024.01.23 |