ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2616
    알고리즘/acmicpc 2015. 10. 3. 00:34

    이런 문제가 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;
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    2405  (0) 2015.10.09
    2437  (0) 2015.10.09
    2463  (0) 2015.09.29
    9079  (0) 2015.09.13
    2465  (0) 2015.09.08

    댓글

Designed by Tistory.