기록

문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 풀이 1) 연속 누적합 dp 우선, 보석의 개수를 신경쓰지 않고, 연속해서 얻을 수 있는 보석의 누적 가치합을 구한다. 이를 위해 세가지 경우를 고려한다. 이전 보석과 연속해서 줍는다. 이전 보석을 버리고, 현재 보석만을 줍는다. 아무 보석도 줍지 않는다. 2) M개 이상의 보석을 줍는다. prefix_sum 2-1. 현재 위치를 포함해서, 왼쪽으로 이동하면서 M개의 보석을 줍는다..