[BOJ/백준] 1823 수확

import sys
sys.setrecursionlimit(20000)


def dfs(left_idx,right_idx,day):
    if left_idx > right_idx:
        return 0
    if dp[left_idx][right_idx] != -1:
        return dp[left_idx][right_idx]

    dp[left_idx][right_idx] = max(dp[left_idx][right_idx], dfs(left_idx+1,right_idx,day+1) + v[left_idx]*day , dfs(left_idx,right_idx-1,day+1) + v[right_idx]*day)
    return dp[left_idx][right_idx]
def input():
    return sys.stdin.readline().rstrip()

N = int(input())

v = [int(input()) for _ in range(N)]

dp = [[-1 for _ in range(N)] for _ in range(N)]


print(dfs(0,N-1,1))

처음 풀었던 방식은 재귀를 이용해서 풀었다. 재귀는 다음과 같다.

left_idx는 현재 왼쪽 논 밭의 위치 right_idx는 오른쪽 논 밭의 위치를 나타낸다. 그리고 day는 현재의 날짜를 나타낸다.

left_idx> right_idx를 넘어가면 0을 return 해준다.

그리고 dp에서 초기값이 아니면 저장된 값을 해준다.

우리는 생각해보면 둘 중 하나를 선택해야한다. 여기서 왼쪽을 먼저 벨지 오른쪽을 먼저 벨지이다.

이 두가지 경우에 대해 재귀를 돌리고 그 결과 중 max값을 현재의 dp에 저장해주면 된다.

 dp[left_idx][right_idx] = max(dp[left_idx][right_idx], dfs(left_idx+1,right_idx,day+1) + v[left_idx]*day , dfs(left_idx,right_idx-1,day+1) + v[right_idx]*day)

현재 저장된 값과 왼쪽을 먼저 갔을때 오른쪽을 먼저깟을때를 구분해서 재귀를 돌려주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

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

dp = [[v[i] *N  if i == j else 0 for i in range(N+1)] for j in range(N+1)]



for y in range(1,N+1):
    for x in range(y-1,0,-1):
        dp[x][y] = max(dp[x+1][y] + v[x] * (N - y + x), dp[x][y-1] + v[y]*(N-y+x))

print(dp[1][N])

두번쨰는 재귀 대신 반복문을 이용해서 푸는 방식이다.

여기서 dp 테이블의 뜻은 x에서 y까지 베었을때의 최대값이다.

먼저 dp를 초기화 시켜줘야한다. 초기화 시켜줄때 i와 j 가 같을때에는 v[i] * N을 해준다.

그 이유는 i번째에서 j번째까지 같을 때 최대값이 되는 경우는 가장 마지막 날에 이 벼를 베는 것이다.

그러므로 이 값으로 초기화를 해준다.

첫번째 풀이는 바깥에서 안쪽으로 베어나가는 느낌으로 풀었다면, 이 풀이는 안쪽에서 바깥쪽으로 베어나가는 느낌으로 푸는 방식이다.

x ->y까지 베었을때의 최대값이 나올 수 있는 경우의 수는

x+1~y를 남겨두고 x를 베었을 때

아니면 x~y-1 를 남겨두고 y를 베었을 때 이다.

그러면 우리는 dp[x+1][y] + v[x] * (N - y + x) 와 dp[x][y-1] + v[y] * (N -y +x)를 비교를 해서 최대값을 저장해주면 된다.