[BOJ] 백준 2616 - 소형기관차

문제 링크

www.acmicpc.net/problem/2616

2616번: 소형기관차

 

풀이

3대의 기관차가 항상 같은 수의 객차를 끌게 됩니다.

결국 N개중 3개의 시작점을 골라 최댓값을 뽑는 문제라고 생각할 수 있습니다.

 

기관차가 끌 수 있는 객차의 수만큼 구간을 잡고, 그 합을 미리 계산해두면 편하게 구현할 수 있습니다.

 

정답 코드

#include <bits/stdc++.h>
 
using namespace std;
 
int d[55'555][3];
int n, k, p[55'555], sum[55'555];
 
int go(int i, int cnt) {
    if (cnt == 3) return 0;
    if (i >= n) return 0;
    int &ret = d[i][cnt];
    if (ret != -1) return ret;
 
    ret = max(go(i + 1, cnt), sum[i] + go(i + k, cnt + 1));
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        sum[0] += p[i];
    }
    for (int i = 1; i + k - 1 < n; i++) {
        sum[i] = sum[i - 1] - p[i - 1] + p[i + k - 1];
    }
 
    memset(d, -1, sizeof(d));
    cout << go(0, 0);
}