DP 와 누적합

코딩테스트에 주요 유형 중 하나는 DP 와 누적합을 이용해서 푸는 문제들이 있다.

 

예제 1) 백준 1912 연속합

www.acmicpc.net/problem/1912

1912번: 연속합

 

N 개의 정수로 구성된 임의의 수열이 주어지고, 이들 중에서 연속된 몇개를 골라서 가장 큰 합을 구하는 문제이다.

이문제는 몇개를 고른다는게 정해져 있지 않고 그냥 구간합 중에서 최대 값이 되는게 얼마냐만 찾으면 되는 그런 문제다

 

- C++

#include <algorithm>
#include <iostream>
 
using namespace std;
 
int N, answer;
int arr[100001], dp[100001];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> arr[i];
    
    dp[0] = arr[0];
    answer = dp[0];
    
    for (int i = 1; i < N; ++i) {
        dp[i] = max(dp[i - 1] + arr[i], arr[i]);
        answer = max(answer, dp[i]);
    }
    
    cout << answer;
    
    return 0;
} 

이 문제를 푸는 핵심 요소는, 이전 인덱스의 값을 누적합에 포함시키느냐 아니냐의 차이이다.

dp[i] = max(dp[i - 1] + arr[i], arr[i]) 가 이점을 잘 보여준다

 

 

 

예제 2) 백준 2208 보석 줍기

www.acmicpc.net/problem/2208

2208번: 보석 줍기

 

DP 와 누적합을 응용하는 문제로, 

이 문제의 경우 먼저, 주어진 배열 값에 대한 prefix sum 을 미리 구해둔다

그리고 M 개 이상을 연속해서 구한것 중에서 최대합을 구해야하는데

미리 구해둔 prefix sum 값에서 M칸 이전의 prefix sum 값을 빼가면서 최대 값을 구해간다

 

M 개 이상의 연속합을 구하면 되기 때문에,

M 칸 전의 연속합들을 빼면서 최대 값을 구하는 그런 방식의 문제다.

 

 

- C++

#include <algorithm>
#include <iostream>
 
using namespace std;
 
int N, M, answer;
int prefix[100001];
 
int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> M;
 
    for(int i = 0; i < N; ++i){
        int num;
        cin >> num;
        prefix[i + 1] = prefix[i] + num;
    }
 
    int previous = 0;
    for(int i = M - 1; i < N; ++i){
        previous = min(previous, prefix[i - M + 1]);
        answer = max(answer, prefix[i + 1] - previous);
    }
 
    cout << answer;
    
    return 0;
}