[백준/BOJ] 백준 2616번 : 소형기관차

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

2616번: 소형기관차

 

2차원 배열 cache에, cache[index][train] = "index위치부터 train개의 소형 기관차를 배치할 수 있을 때, 최대 손님 수"를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다

 

코드

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

int n;
int people[50005];
int psum[50005];
int cache[50005][4]; //[index][train] = index위치부터 train개의 소형 기관차를 배치할 수 있을때, 최대 손님 수
int max_cnt;

void pre() {
	for (int i = 0; i < 50005; i++) {
		for (int j = 0; j < 4; j++) {
			cache[i][j] = -1;
		}
	}
}

int solve(int index, int train) {

	if (index >= n + 1) {
		return 0;
	}

	//더 이상 소형 기관차를 배치할 수 없을때
	if (train <= 0) {
		return 0;
	}

	int& ret = cache[index][train];

	if (ret != -1) {
		return ret;
	}

	ret = 0;

	//index에  소형 기관차를 배치할때
	ret = max(ret, psum[min(index + max_cnt - 1, n)] - psum[index - 1] + solve(min(index + max_cnt - 1, n) + 1, train - 1));

	//index에 소형 기관차를 배치하지 않을때
	ret = max(ret, solve(index + 1, train));

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	pre();

	cin >> n;

	for (int i = 1; i <= n; i++) {
		int input;
		cin >> input;

		people[i] = input;
		psum[i] = psum[i - 1] + people[i];
	}

	cin >> max_cnt;

	int result = solve(0, 3);

	cout << result;

	return 0;
}