[백준 2616] 소형기관차 (C++)

2616번: 소형기관차

 

 

현재 칸을 선택할 때, 선택하지 않을 때를 정해서 재귀를 수행하면 되는 문제이다.

 

현재 칸을 선택하지 않는다면 현재 칸의 번호를 +1 한 채로 다음 칸으로 넘어간다.

 

현재 칸을 선택한다면?

현재 칸부터 소형 기관차의 크기만큼 연속된 칸에 타있는 손님의 수를 누적합 배열 parr을 통해서 구해준다. 그리고 현재 칸의 번호를 +소형기관차의크기 한 채로 다음 칸으로 넘어간다.

 

기저 조건은 소형 기관차를 선택한 횟수가 4가 되거나 현재 칸을 선택해도 소형 기관차의 크기만큼 남은 칸이 없을 때이다.

 

 

 

#include <iostream>
#include <cstring>
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
using namespace std;
 
int N, TN;
int parr[50001];
int dp[4][50001];
 
void input(){
    cin >> N;
    int a;
    for(int i = 1; i <= N; i++){
        cin >> a;
        parr[i] = a + parr[i-1];
    }
    cin >> TN;
    
    memset(dp, -1, sizeof(dp));
}
 
int solve(int tn, int con){
    if(tn == 4 || con > N) return 0;
    
    int &ret = dp[tn][con];
    if(ret != -1) return ret;
    
    ret = 0;
    
    ret = max(solve(tn, con+1), solve(tn+1, con+TN) + parr[con] - parr[con - TN]);
    
    return ret;
}
 
int main(){
    fastio
    input();
    cout << solve(1, TN);
    
    return 0;
}