[백준 2616] 소형기관차

문제링크 : https://www.acmicpc.net/problem/2616

💻 문제 풀이 : C++

#### 풀이 1번

#include <iostream>
#include <algorithm>

using namespace std;

int guest[50010];
// i번째 소형기관차가 j번째까지 보았을 때, 최대로 운송할 수 있는 승객 수
int dp[4][50010];

int main()
{
	int N, M, input;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> input;
		guest[i] = input + guest[i - 1];
	}
	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], dp[i - 1][j - M] + guest[j] - guest[j - M]);
		}
	}
	cout << dp[3][N] << "\n";

	return 0;
}

📌 memo 😊

---

ref)
👍 X 2000
https://comyoung.tistory.com/184