구간의 시작과 끝중 하나를 선택할 수 있는 다이나믹 프로그래밍

1823번: 수확

 

왼쪽부터 오른쪽으로 n개의 벼가 있는데, 매번 맨 왼쪽 혹은 맨 오른쪽 중 하나를 수확할 수 있다

 

k번째 수확할때 그 벼의 가치가 A[i]라면, A[i] * k의 이익을 얻는다

 

n개의 벼를 모두 수확할 때 얻는 최대 이익은?

 

---------------------------------------------------------------------------------------------------------------------------------------------------

 

dp[i][j]를 [i,j] 구간에서 벼를 수확할 때 얻는 최대 이익이라고 정의

 

i번째 벼를 수확하거나, j번째 벼를 수확할 수 있다

 

[i,j] 구간에 벼가 있다면 0 ~ i-1의 벼랑 j+1 ~ n-1 벼는 이미 수확했으므로, i + (n-1) - (j)개의 벼를 수확했으므로

 

현재는 n - 1 - j + i + 1 = n-j+i번째 벼를 수확하는 것이다

 

i번째 벼를 수확한다면 A[i] * (n-j+i) 이익을 얻고 j번째 벼를 수확한다면 A[j] * (n-j+i) 이익을 얻는다

 

i번째 벼를 수확한다면 이제 남아있는 구간은 [i+1,j] 구간이고 여기서 얻는 이익은 dp[i+1][j]이므로

 

[i,j] 구간에서 얻는 최대 이익은 이 둘의 합인 dp[i][j] = A[i]*(n-j+i) + dp[i+1][j]

 

j번째 벼를 수확한다면 이제 남아있는 구간은 [i,j-1] 구간이고 여기서 얻는 이익은 dp[i][j-1]이므로

 

dp[i][j] = A[j]*(n-j+i) + dp[i][j-1]

 

둘 중 더 큰 값을 선택하면 된다.

 

초기화는 벼가 하나밖에 없는 경우, 즉 i = 0,1,2,..,n-1에 대해 dp[i][i]값

 

벼가 i번째 벼 하나만 남아있다면 이 벼는 n번째 수확하는 벼이므로 dp[i][i] = A[i]*n

 

구하고자 하는 값은 [0,n-1]에서 얻는 최대 이익 dp[0][n-1]이다

 

dp를 채울때는 i = 0,1,2,..,n-1, j = i,i+1,...,n-1 순으로 채우면 dp[0][n-1] 시도하고 dp[1][n-1],... 이렇게 차니까 안될거잖아

 

i = n-1,n-2,...,0으로 반대로 순회하고 j = i,i+1,..,n-1 순으로 순회하면 마지막에 dp[0][n-1]을 구하게 된다

 

점화식은 

 

dp[i][j] = max( A[j]*(n-j+i) + dp[i][j-1], A[i]*(n-j+i) + dp[i+1][j], dp[i][j])일텐데

 

i+1 >= n인 경우는 dp[i+1][j]를 구할 수 없으니 dp[i][j] = max( A[j]*(n-j+i) + dp[i][j-1], dp[i][j])

 

j-1 < 0인 경우는 dp[i][j-1]을 구할 수 없으니 dp[i][j] = max(A[i]*(n-j+i) + dp[i+1][j], dp[i][j])

 

n = int(input())

A = []

for _ in range(n):
    
    m = int(input())
    A.append(m)

#dp[i][j]:[i,j]에 있는 벼들로 얻을 수 있는 최대이익
dp = [[0]*n for _ in range(n)]

for i in range(n):
    
    dp[i][i] = A[i]*n

for i in range(n-1,-1,-1):
    
    for j in range(i,n):
        
        k = i + n-1-j + 1

        if i+1 <= n-1 and j-1 >= 0:

            dp[i][j] = max(dp[i][j],dp[i][j-1] + A[j]*k,dp[i+1][j] + A[i]*k)
        
        elif i+1 <= n-1:
            
            dp[i][j] = max(dp[i][j],dp[i+1][j] + A[i]*k)
        
        elif j-1 >= 0:
            
            dp[i][j] = max(dp[i][j-1],dp[i][j-1] + A[j]*k)
            
print(dp[0][n-1])

 

 

근데 이제 이렇게 잘못 생각할 수도 있다

 

[i,j] 구간에서 i를 선택하면 i번째 선택하면 얻는 비용 A[i]*(n-j+i) 에다가

 

이제 [i,j] 이전 구간은 [i-1,j]에서 i-1번을 선택한 경우, [i,j+1]에서 j+1번을 선택한 경우이므로,

 

dp[i][j] = max(dp[i-1][j],dp[i][j+1]) + max(A[i]*(n-j+i),A[j]*(n-j+i)) 이거 아닌가?

 

근데 정의를 좀 생각해보면

 

[i,j] 구간에서 얻는 최대 이익을 dp[i][j]라고 정의했는데

 

i번째를 선택하면 A[i]*(n-j+i)를 얻고 이제 남은 구간은 [i+1,j]이고, 여기서 얻은 최대 이익 dp[i+1][j]을 더해야

 

[i,j]구간에서의 최대 이익 dp[i][j]가 되겠지