[Gold III] 수확 - 1823

문제 링크

성능 요약

메모리: 199508 KB, 시간: 472 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 12월 28일 23:41:41

문제 설명

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과 벼의 가치가 주어져 있을 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다.

출력

첫째 줄에 얻을 수 있는 최대 이익을 출력한다.

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/1823
import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline
 
 
n = int(input())
a = list()
 
for i in range(n):
    a.append(int(input()))
    
    
dp = list([-1] * n for i in range(n))
 
# print(*dp2, sep = '\n')
 
def max_rice(s,e):
    if s  == e:
        return n * a[s]
    
    if dp[s][e] == -1:
        k = n - (e - s) #n이, 리스트 크기가 4 라고 하자. s = 0, e = 3. k = 1이여야 한다
        
        if dp[s + 1] [e] == -1:
            left = k * a[s] + max_rice(s + 1, e)
        else:
            left = k * a[s] + dp[s+1][e]
        
        
        
        if dp[s] [e -1] == -1:
            right = k * a[e] + max_rice(s, e - 1)
        else:
            right = k * a[e] + dp[s][e - 1]
        
        
        dp[s][e] = max(left, right)
        
       
       
 
    return dp[s][e]
    
   
 
 
print(max_rice(0, n - 1))