BOJ 2616 C++

문제접근

dp와 누적합을 이용해야 합니다.
우선 객차에서의 손님의 수를 누적합으로 저장합니다.

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

이제 dp로 다음과 같은 원리를 사용하면 됩니다.
예제에서 처럼 두 객차만큼 끌 수 있다고 할때 제일 많은 손님을 끄는 경우를 구하는 코드는 다음과 같습니다.

for (int i = 1; i <= n; i++)
{
    dp[i] = max(dp[i - 1], (t[i] - t[i - s]));
}
//s는 소형 기관차가 최대로 끌 수 있는 객차의 수

지금 i에서의 s만큼의 객차를 끌고 갈때와 전에 구했던 것과 비교하는 것입니다.
그럼 dp[7]에서는 첫번째에서 가장 많이 끌고갈 수 있는 수를 알 수 있네요. 105입니다.
이를 응용해서 다음과 같은 코드로 하면 됩니다.

int dp[4][50001];

for (int i = 1; i <= 3; i++)
	{
		for (int j = i * s; j <= n; j++)
		{
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - s] + (t[j] - t[j - s]));
		}
	}

이 코드를 실행시키면 다음과 같은 결과가 나옵니다.

//dp[4][50001]
//dp[1][1]~dp[3][7]
0 75 90 90 90 90 105
0 0 0 135 135 165 195
0 0 0 0 0 210 240

dp[i-1][j-s]즉 첫번째 기차가 끌고 갔기에 선택할 수 없는 부분입니다. 이미 i가 1일때

0 75 90 90 90 90 105

각 구간에서 끌고 갈 수 있는 최대로 초기화 되었기 때문에. j가 4면 j - s즉 4에서 끌고 갈 수 있는 객차 손님수 누적합에서 가져올 수 있습니다.
요약하면 원리는 이렇습니다.

지금까지 가장 많이 끌고간것 + j에서의 누적합

코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;
int t[50001];
int dp[4][50001];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> t[i];
		t[i] += t[i - 1];
	}
	int s; cin >> s;
	for (int i = 1; i <= 3; i++)
	{
		for (int j = i * s; j <= n; j++)
		{
			dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - s] + (t[j] - t[j - s]));
		}
	}
	cout << dp[3][n];
}