백준 소형기관차, (c++) 2616

문제

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

해결법

• 3개의 소형객차를 사용해서 최대로 많은 손님을 이끌고 가야한다.

• 여기서 dp식은 dp[i][j]이다 -> 현재 i까지 바라보고 있는데 소모한 소형기관차는 j이다

• dp[i][j] = max(dp[i-1][j], dp[i - k][j -1] + s[i] - s[i -k]);

주의

• dp[i][j]에서 1 ~ k번객차까지 봤다는 dp[k]가 있어야하므로 idx - k == 0인 부분도 보아야한다 .

  소스

#include <bits/stdc++.h>

using namespace std;

int n;
int Sequential;
int a[51000]; // 각 객차에서 손님의 수 
int _sum_a[51000]; //a의 누적합 
int dp[51000][4]; // dp[i][j] => 현재 i번째 객차를 바라보고 j개의 소형기관차를 사용할때 최대 손님 수 
//dp[k][x] -> 1번부터 k번객체까지 차지해야하는 경우, s[k] - s[0]이 1번부터 k번까지 객차 합
//1차원배열쪽에 k가 들어가야한다 그래야지 k번객차까지 다 본 것이니, -> k가 들어가기 위해서는  dp[0]도 봐야해서  idx - k == 0인 경우도 고려해야한다 
//dp[i][j] = max(dp[i-1][j], dp[i-k][j-1] + s[i] - s[i-k]);

int k;//한번에 최대로 끌 수 있는 객차의 수 
int solve(int idx, int cnt)
{
    if (dp[idx][cnt] != -1) return dp[idx][cnt];


    //check! idx - k가 0일때도 체크해야한다 왜???!!!
    //dp[k][1] 일 수도있으니 
    if (idx - k < 0) return 0;

    if (idx < 1 || cnt < 1) return 0;

    dp[idx][cnt] = max(solve(idx - 1, cnt), solve(idx - k, cnt - 1) + (_sum_a[idx] - _sum_a[idx - k]));

    return dp[idx][cnt];
}
int main()
{

    memset(dp, -1, sizeof(dp));

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    cin >> k;

    for (int i = 1; i <= n; i++)
    {
        _sum_a[i] = _sum_a[i - 1] + a[i];
    }


    cout << solve(n, 3) << endl;
    return 0;
}