18231 [백준 1823번] 수확 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 벼가 한 줄로 쭉 세워져 있고, 벼의 가치는 각각 입력으로 들어옵니다. 벼를 나중에 수확할수록 이익을 더 얻기 때문에, 끝까지 가 봐야 알 수 있으므로 그리디 방식으로는 해결할 수 없습니다. 이 문제의 경우, DP를 이용하여 접근할 수 있습니다. 보통 DP 문제의 경우 맨 마지막 값이 정답이 되는데, 이 문제의 경우 배열의 앞과 뒤를 좁혀 가며 탐색을 하므로, 중간의 어느 지점이 맨 마지막에 탐색하.. 2021. 9. 29. 이전 1 다음
