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

www.acmicpc.net/problem/2616

2616번: 소형기관차

[풀이]

DP로 풀 수 있는 문제였다.

DP[x][y]: x번째 소형 기관차가 y번째 객차를 끌고갈 경우

x번째 기관차가 y번째 객차를 끌고가는 경우와 끌고가지 않는 경우를 비교해 줘야 한다.

train[]에 해당 인덱스까지의 누적 인원수를 저장한다.

res = max(solution(x,y+1), train[y + M - 1] - train[y - 1] + solution(x+1,y+M))

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int N, M;
int train[50001];
int DP[3][50001];

int solution(int x, int y) {
	if (x == 3 || y >= N)
		return 0;
	
	int& res = DP[x][y];
	if (res != -1)
		return res;
	res = 0;
	if (y + M - 1 <= N)
		res = max(solution(x, y + 1), train[y + M - 1] - train[y - 1] + solution(x + 1, y + M));
	
	return res;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int tmp;
		cin >> tmp;
		train[i] = train[i - 1] + tmp;
	}
	cin >> M;
	memset(DP, -1, sizeof(DP));
	cout << solution(0, 1) <<'\n';
	return 0;
}