[백준 1823번] 수확

난이도: 골드 III

문제 링크: https://www.acmicpc.net/problem/1823

1823번: 수확

백준 1823번 문제 수확

벼가 한 줄로 쭉 세워져 있고, 벼의 가치는 각각 입력으로 들어옵니다.

벼를 나중에 수확할수록 이익을 더 얻기 때문에, 끝까지 가 봐야 알 수 있으므로 그리디 방식으로는 해결할 수 없습니다.

 

이 문제의 경우, DP를 이용하여 접근할 수 있습니다.

보통 DP 문제의 경우 맨 마지막 값이 정답이 되는데, 이 문제의 경우 배열의 앞과 뒤를 좁혀 가며 탐색을 하므로, 중간의 어느 지점이 맨 마지막에 탐색하는 지점이 됩니다. 따라서 맨 마지막에 수확하는 지점이 어디인지 파악하는 것이 중요합니다.

따라서 수확하는 두 지점 left, right를 두고, left > right가 되면 0을 return 하도록 합니다.

 

2차원 배열 dp를 만들어 두고, dp[left][right] = 주어진 구간 [left, right] 내에서 수확 시 지금까지 얻은 최댓값을 담게 됩니다.

이미 값을 가지고 있는 경우, 해당 값을 return 하면 됩니다.

 

값이 아직 기록되지 않은 경우, 함수를 재귀적으로 호출하게 됩니다.

dp[left][right]의 값은 [(현재 맨 왼쪽의 값에 count를 곱한 값) + (left + 1부터 right까지의 dp값)]과 [(현재 맨 오른쪽의 값에 count를 곱한 값) + (left부터 right - 1까지의 dp값)] 중 더 큰 값이 됩니다.

즉 점화식은 dp[left][right] = max(get_dp(left+1, right, count+1) + (rice[left] * count), get_dp(left, right-1, count+1) + (rice[right] * count)) 가 됩니다.

 

이번 문제는 기존의 다른 dp 문제들과 약간 달라서 접근하는 재미가 있었어요.

채점 결과

right-1을 right+1로 써서 한번 틀린거 외에는 큰 어려움은 없었습니다.

 

참고한 글:

• https://husk321.tistory.com/217