백준 2616번 : 소형기관차

  '뭐야? 이 문제 쉽잖아? 살짝 변형하면 어디서 본 것 같은데?'라고 생각했다가 '시간 초과'나고 '틀렸습니다' 뜨고... ㅎㅎ 왜 항상 어디서 본 것 같은데 틀리는 것일까... 흠...

---

  풀이

  처음에 dp를 정할 때 조금 헷갈렸다. 보통 변하는 값 2개를 dp의 한 축으로 두는 경우가 많아서 '소형 기관차의 개수는 3개로 고정이니까 그거 말고 다른 것을 dp의 축으로 둬야지 ^^!'라고 생각한 게 오판이었다.

 

dp [i][j] : 소형 기관차가 i개 있고 객실이 j번까지 있을 때 운송가능한 최대 승객 수

 

  그 외의 변수를 정의하고 가면

 

n : 총 객실 수

m : 소형기관차가 끌 수 있는 최대 객실 수

sum [k] : 1번 객실부터 k번 객실까지 승객의 총합

 

  소형 기관차가 i-1개였다가 1개 추가되서 i개가 되는 상황을 생각해보자. i번째 소형기관차는 최대 m개의 객실을 끌 수 있으므로 j-m+1번 객실부터 j번 객실 까지를 운송할 수 있다. 그리고 나머지 1번부터 j-m번 객실은 기존의 i-1개의 소형기관차가 운송하면 된다.

 

dp [i][j] = sum [j] - sum [j-m] + dp [i-1][j-m]

 

  하지만 i번째 소형 기관차가 j-m+1번부터 j번까지의 객실을 끄는 것이 최선이 아닐 수도 있다. 다시 말해 j번째 객실을 운송하지 않는 것이 최선일 수도 있다.

 

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

 

#include <iostream>

using namespace std;

int n, m;
int seq[50002];
int dp[4][50002];
int sum[50002];

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> seq[i];
        sum[i] = sum[i-1] + seq[i];
    }
    cin >> m;

    for(int i = 1; i <= 3; i++)
    {
        for(int j = i*m; j <= n; j++)
        {
            dp[i][j] = max(dp[i][j-1], sum[j] - sum[j-m] + dp[i-1][j-m]);
        }
    }
    
    cout << dp[3][n];
        
    return 0;
}