[C++] 2208 - 보석 줍기 (골드2)

1. 문제 설명

2208번: 보석 줍기

 

---

2. 아이디어

 

경우의 수를 묻는 문제는 보통 dp로 찔러보면 된다.

연속합과 관련된 문제인 건 알겠는데, 생각보다 까다로운 문제였었다.

 

내가 사용한 방법은 우선 차례대로 모든 보석을 주웠을 때의 합을 차례로 구한다.

그 후, m간격 만큼 이동하면서 이전의 값을 빼주면 계속해서 m구간 만큼의 구간합을 알 수 있다.

이렇게 했을 때, 최대값을 출력하면 해결되는 문제였다.

 

---

3. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    int cache[100001];
    int pickUp = 0, cost = 0;
    int min_value = 0, max_value = 0;
    for (int i=1; i<=n; i++) { // 1~n부터 계속 주운 값을 cache에 넣는다.
        cin >> pickUp;
        cost += pickUp;
        cache[i] = cost;
    }
    for (int i = m-1; i < n; i++) {
        min_value = min(min_value, cache[i - (m-1)]);
        max_value = max(max_value, cache[i + 1] - min_value);
    }
    cout << max_value;

    return 0;
}