[백준 1823번] 수확 (python)

문제

1 × N 크기의 긴 밭에 벼가 심어져 있다. 준희는 이 벼를 수확 하려고 한다. 그런데 가운데 있는 벼를 수확을 하려면 끝에서 가운데까지 헤집고 들어가야 하므로 양 끝에 있는 벼만 수확을 할 수 있다. 처음에는 첫 번째와 N번째 벼를 수확을 할 수 있을 것이며 만약에 첫 번째 벼를 수확을 하였다면 두 번째 벼와 N번째 벼를 수확을 할 수 있다.

수확을 하였을 때 얻을 수 있는 이익은 다음과 같다. 만약에 그 벼의 가치가 v(i)라고 하고 그 벼를 k번째로 수확을 한다고 하면 v(i) × k 만큼의 이익을 얻게 된다.

만약에 벼의 가치가 차례로 1 3 1 5 2 라고 하고 첫 번째, 다섯 번째, 두 번째, 세 번째, 네 번째의 순서대로 수확을 한다고 하면 1×1 + 2×2 + 3×3 + 4×1 + 5×5 = 43 이 되어 43 만큼의 이익을 얻게 된다. 그리고 이 값이 저 벼로 얻을 수 있는 최대 이익이 된다.

우리가 구해야 할 값은 다음과 같다. 벼의 개수 N과 벼의 가치가 주어져 있을 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

 

기록

(dp 18일차) 어렵다.. 가끔 해결할 수 없는 메모리초과 때문에 너무 화났었는데 이제야 이유를 알았다. setrecursionlimit 사용해서 최대 재귀 깊이를 항상 생각없이 10**9로 설정했는데 알고보니 이 것 때문에 메모리 초과가 발생한 것이었다...!! 문제에서 발생할 수 있는 최대 깊이인 2000으로 설정해주니까 성공했다. 생각지도 못한 이유!

 

이번 문제는 top down 방식으로 메모이제이션을 사용해서 풀었다. 함수 인자로 갈 수 있는 양 끝의 인덱스를 받아, 각 끝을 하나씩 줄이면서 다음 함수를 호출하고 해당 범위에서의 최대 이익을 반환하는 재귀 함수를 구현했다. 이 때, 각 범위의 양 끝 인덱스로 최대 이익을 이차원 배열 dp에 저장하며 중복 호출 시 반환하도록 하였다. 따라서 dp[i][j]는 i~j 범위의 최대 이익을 저장하게 된다.

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2000)

n = int(input())
rice = [int(input()) for i in range(n)]

dp =[[0 for i in range(n)] for i in range(n)]
def get_maxvalue(s, e, cnt):
    # base case
    if s==e : return cnt*rice[s]
    if dp[s][e] : return dp[s][e]
    # step
    dp[s][e] = max(get_maxvalue(s+1, e, cnt+1)+cnt*rice[s], get_maxvalue(s, e-1, cnt+1)+cnt*rice[e])
    return dp[s][e]

print(get_maxvalue(0, n-1, 1))

1.  i~j 범위의 최대 이익을 저장하는 이차원 배열 dp 생성

2. s~e 범위의 최대 이익을 반환하는 재귀 함수 구현

- 범위의 양 끝을 dp 배열의 인덱스로 저장하는 메모이제이션 사용

- 최대 이익은 (s+1~e 범위의 이익) + (s의 이익), (s~e-1 범위의 이익) + (e의 이익)으로 나눠 더 큰 값을 저장한다.

3. 위의 함수를 사용하여 전체 범위의 최대 이익을 출력한다.