2616

이런 문제가 2003년 초등부 올림피아드에 나왔으니 내가 당시 초등학교 6학년이었으니까,, 감히 이런걸 푼다고 상상도 했을까... 이런 문제를 푸는 괴물들도 있었겠지. 나는 이걸 대학생이 되어서야 풀게 되었다.

이 문제는 DP문제이다. 어떻게 DP를 구현하느냐에 따라서 해결 방법이 천차 만별이다.

총 세개의 기관차를 쓰는게 이 문제를 푸는데 핵심이다.

처음에는 각 구간별로 n개의 소형기관차를 썼을 때 최대 값을 구하는 함수를 사용했다. 하지만 이건 배열을 여러번 탐색해야해서(O(N^n)) 시간초과가 뜬다.

어떻게 해야할지 고민하다가 세개의 기관차를 사용하는 것에서 방법을 찾았다.

먼저 현재 위치에서 소형차기관차를 연결했을 때 태울 수 있는 승객을 저장하는 배열을 만든후 d[0][50000]에 넣어둔다.

그 후 d[1][50000]은 이전 d[0]에 넣은 것들에서 현재 소형 기관차 앞에 있는 객차중 소형기관차를 연결 했을 떄 최대가 되는 것들을 찾는다. 그러면 d[1][50000]은 소형 기관차 두 개를 연결 했을 때 손님의 객수를 최대로 하는 방법이다.

마지막으로 d[2][50000]은 d[1]에 넣은 것들에서 현재 소형기관차 뒤에 있는 객차중 소형기관차를 연결 했을 때 최대가 되는 것들을 찾는다. 이전에 앞에 있는 객차들 중에서 찾았기 때문에 지금은 뒤에있는 것들에서 찾아야 중복이 되지 않는다.

만약 4개의 소형기관차를 사용한다면 위 알고리즘을 사용할 수 없다. 시간초과가 뜬 원래 알고리즘을 사용할 수밖에.

 
#include<cstdio>
#include<iostream>

#include<fstream>

using namespace std;

int d[3][50000];
int partialSum[50005];
int length;
int N;


int main(){
	int tmp;
	int res=0;

	ifstream ifp("input.txt");

	ifp>>N;
	//scanf("%d", &N);
	for(int i=1; i<=N; i++){
		ifp>>tmp;
		//scanf("%d", &tmp);
		partialSum[i] = partialSum[i-1]+tmp;
	}

	ifp>>length;
	//scanf("%d", &length);

	for(int piv=1; piv<=N-length+1; piv++){
		d[0][piv]=partialSum[piv+length-1]-partialSum[piv-1];
	}

	
	int partialMax=0;
	for(int piv=1; piv<=N-length+1; piv++){
		int addable = piv-length;
		if(addable > 0){
			partialMax = max(d[0][addable], partialMax);
		}
		d[1][piv] = d[0][piv] + partialMax;
	}

	partialMax = 0;
	for(int piv=N-length+1; piv>=1; piv--){
		int addable = piv+length;
		if(addable <= N-length+1){
			partialMax = max(d[0][addable], partialMax);
		}
		d[2][piv]=d[1][piv] + partialMax;

		res = max(res, d[2][piv]);
	}
	
	printf("%d\n", res);
	return 0;
}