[백준] 2208 - 보석 줍기

https://www.acmicpc.net/problem/2208

2208번: 보석 줍기

 

문제를 해석해 보면,

N개의 요소를 가지는 배열중 m개 이상의 연속된 부분 집합 중 최대 합

을 구하는 문제이다.

 

일반적인 부분 합 문제로 풀려면 O(N^2)의 시간 복잡도가 소요돼 실패한다.

따라서 dp를 이용해 풀 것이다.

 

dp[i] = i번째 요소의 부분집합 중 m개 이상의 연속된 집합의 최대 합

으로 정의하자.

 

그렇다면 dp 배열은 다음과 같은 두 가지 상황이 있다.

1. 현재 i번째 인덱스의 요소를 추가하는 경우( dp[i - 1] + a[i] )
2. 현재 인덱스에서 앞으로 m개의 인덱스의 합을 세는 경우( sum[i] - sum[i - m] )

 

따라서 완성된 점화식은 다음과 같다.

dp[i] = max(dp[i - 1] + a[i], sum[i] - sum[i - m])

문제를 풀 때에는 변수 하나로 배열 하나를 줄였다.

 

#include <iostream>
using namespace std;

int a[100001], dp[100001], n, m;

int main() {
    cin >> n >> m;

    int ans = 0, mindp = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = dp[i - 1] + a[i];

        if (i >= m) {
            mindp = min(mindp, dp[i - m]);
            ans = max(ans, dp[i] - mindp);
        }
    }
    cout << ans;
}