[KOITP] Assembly Line Scheduling

출처 : http://www.koitp.org/problem/ASSEMBLY_LINE_SCHEDULING/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	441	133 (30%)	120

문제

명우네 공장에는 두 개의 생산라인이 있고, 각 라인에는 $n$개의 공정이 순서대로 있다. 하나의 제품이 완성이 되려면 두 생산라인 중 한 생산라인을 정해, 그 생산라인에 미완성 제품이 들어가고 그 생산라인의 $n$개의 공정을 순서대로 지나, 생산라인에서 생산을 마무리하여 완성된다. 중간에 생산라인을 바꿀 수도 있다.

첫 번째 생산라인의 $i$번째 공정에서 소요되는 시간은 $S_{1,i}$이고, 두 번째 생산라인의 $i$번째 공정에서 소요되는 시간은 $S_{2,i}$이다. 그리고 첫 번째 생산라인에 진입하는 시간은 $e_1$, 두 번째 생산라인에 진입하는 시간은 $e_2$이고, 첫 번째 생산라인에서 생산을 마무리 하는 시간은 $x_1$, 두 번째 생산라인에서 생산을 마무리 하는 시간은 $x_2$이다. 마지막으로 첫 번째 생산라인의 $i$번째 공정을 마치고 두 번째 생산라인으로 바꾸는데 걸리는 시간은 $t_{1,i}$이고, 두 번째 생산라인의 $i$번째 공정을 마치고 첫 번째 생산라인으로 바꾸는데 걸리는 시간은 $t_{2,i}$이다. 즉, 명우의 공장은 아래와 같은 그림으로 표현된다.

명우는 자신이 만들어놓은 공장에서 하나의 제품을 만드는데 걸리는 최소 시간을 알고 싶어한다. 명우를 도와 하나의 제품을 만드는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫 줄에 라인별 공정의 개수 $n$, 라인별 진입 시간과 마무리 시간 $e_1$, $e_2$, $x_1$, $x_2$가 주어진다. ($2\le n\le 300,000$, $1\le e_1,e_2,x_1,x_2\le 200$)

두 번째 줄에 $S_{1,1},S_{1,2},\dots ,S_{1,n}$를 나타내는 $n$개의 자연수가 공백으로 구분되어 주어진다. ($1\le S_{1,i}\le 200$)

세 번째 줄에 $S_{2,1},S_{2,2},\dots ,S_{2,n}$를 나타내는 $n$개의 자연수가 공백으로 구분되어 주어진다. ($1\le S_{2,i}\le 200$)

네 번째 줄에 $t_{1,1},t_{1,2},\dots ,t_{1,n-1}$를 나타내는 $n-1$개의 자연수가 공백으로 구분되어 주어진다. ($1\le t_{1,i}\le 200$)

다섯 번째 줄에 $t_{2,1},t_{2,2},\dots ,t_{2,n-1}$를 나타내는 $n-1$개의 자연수가 공백으로 구분되어 주어진다. ($1\le t_{2,i}\le 200$)

출력

첫 줄에 하나의 제품을 만드는데 걸리는 최소 시간을 출력한다.

힌트

입력 예제

6 2 4 3 2
7 9 3 4 8 4
8 5 6 4 5 7
2 1 1 3 4 
2 1 2 2 1

출력 예제

38

package algo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class AssemblyLineScheduling {
    
    public static int N = 0;		// 공정개수
    
    public static int e1 = 0;		// 1라인 진입 시간
    public static int e2 = 0;		// 2라인 진입 시간
    public static int x1 = 0;		// 1라인 마무리 시간
    public static int x2 = 0;		// 2라인 마무리 시간
    
    public static int S1[] = null;	// 1라인 공정소요 시간
    public static int S2[] = null;	// 2라인 공정소요 시간
    
    public static int t1[] = null;	// 1라인에서 2라인으로 변경시간
    public static int t2[] = null;	// 2라인에서 1라인으로 변경시간
    
    public static int cache1[] = null; 	// 1라인 idx 지점까지의 최소시간
    public static int cache2[] = null; 	// 2라인 idx 지점까지의 최소시간

    public static void main(String[] args) throws Exception {
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	StringTokenizer st = new StringTokenizer(br.readLine());
	N = Integer.parseInt(st.nextToken());	// [ 2, 300,000 ]
	
	e1 = Integer.parseInt(st.nextToken());
	e2 = Integer.parseInt(st.nextToken());
	x1 = Integer.parseInt(st.nextToken());
	x2 = Integer.parseInt(st.nextToken());	// [ 1, 200 ]
	
	S1 = new int[N+1];
	S2 = new int[N+1];		// [ 1, 200 ]
	
	t1 = new int[N];
	t2 = new int[N];			// [ 1, 200 ]
	
	cache1 = new int[N+1];
	cache2 = new int[N+1];
	
	st = new StringTokenizer(br.readLine());
	for (int i = 1 ; i <= N ; i++) {
	    S1[i] = Integer.parseInt(st.nextToken());
	}
	
	st = new StringTokenizer(br.readLine());
	for (int i = 1 ; i <= N ; i++) {
	    S2[i] = Integer.parseInt(st.nextToken());
	}
	
	st = new StringTokenizer(br.readLine());
	for (int i = 1 ; i < N ; i++) {
	    t1[i] = Integer.parseInt(st.nextToken());
	}
	
	st = new StringTokenizer(br.readLine());
	for (int i = 1 ; i < N ; i++) {
	    t2[i] = Integer.parseInt(st.nextToken());
	}
	
	for (int idx = 1 ; idx <= N ; idx++) {
	    
	    for (int line = 1 ; line <= 2 ; line++){
		
		if (idx == 1) {
		    if (line == 1) {
			cache1[1] = e1 + S1[1];
		    } else {
			cache2[1] = e2 + S2[1];		// 기저 케이스
		    }
		} else {
        	    if (line == 1) {   
        		cache1[idx] = Math.min(cache1[idx-1], cache2[idx-1] + t2[idx-1]) + S1[idx];
        	    } else { 
        		cache2[idx] = Math.min(cache2[idx-1], cache1[idx-1] + t1[idx-1]) + S2[idx];
        	    }
		}
	    }
	}
	
	int answer = Math.min(cache1[N] + x1, cache2[N] + x2);
	
	bw.write(String.valueOf(answer));
	bw.flush();
	bw.close();
    }
}

< Comment >

 처음에는 함수를 만들어서 함수를 부를 때마다 이전의 최소합을 구하는 방식으로 진행했었습니다. 그러나 해당 방식으로 풀었을 경우에는 저로써는 1초라는 시간을 도저히 맞출수가 없었기 때문에 결국, 반복문을 통하여 풀이한 값들을 저장하는 방식으로 제한시간을 통과할 수 있었습니다. 생각하기가 조금 난해하다면, 함수로 풀어놓고 변경하는 것도 방법일 것 같습니다.

 아래쪽이 처음 풀었던 코드입니다. 내용상으로는 같습니다.

package algo;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class AssemblyLineScheduling {
     
    public static int N = 0;        // 공정개수
     
    public static int e1 = 0;       // 1라인 진입 시간
    public static int e2 = 0;       // 2라인 진입 시간
    public static int x1 = 0;       // 1라인 마무리 시간
    public static int x2 = 0;       // 2라인 마무리 시간
     
    public static int S1[] = null;  // 1라인 공정소요 시간
    public static int S2[] = null;  // 2라인 공정소요 시간
     
    public static int t1[] = null;  // 1라인에서 2라인으로 변경시간
    public static int t2[] = null;  // 2라인에서 1라인으로 변경시간
     
    public static int cache1[] = null;  // 1라인 idx 지점까지의 최소시간
    public static int cache2[] = null;  // 2라인 idx 지점까지의 최소시간
 
    public static void main(String[] args) throws Exception {
         
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());   // [ 2, 300,000 ]
         
        e1 = Integer.parseInt(st.nextToken());
        e2 = Integer.parseInt(st.nextToken());
        x1 = Integer.parseInt(st.nextToken());
        x2 = Integer.parseInt(st.nextToken());  // [ 1, 200 ]
         
        S1 = new int[N+1];
        S2 = new int[N+1];      // [ 1, 200 ]
         
        t1 = new int[N];
        t2 = new int[N];            // [ 1, 200 ]
         
        cache1 = new int[N+1];
        cache2 = new int[N+1];
         
        st = new StringTokenizer(br.readLine());
        for (int i = 1 ; i <= N ; i++) {
            S1[i] = Integer.parseInt(st.nextToken());
        }
         
        st = new StringTokenizer(br.readLine());
        for (int i = 1 ; i <= N ; i++) {
            S2[i] = Integer.parseInt(st.nextToken());
        }
         
        st = new StringTokenizer(br.readLine());
        for (int i = 1 ; i < N ; i++) {
            t1[i] = Integer.parseInt(st.nextToken());
        }
         
        st = new StringTokenizer(br.readLine());
        for (int i = 1 ; i < N ; i++) {
            t2[i] = Integer.parseInt(st.nextToken());
        }
         
        int answer = Math.min(dp(1, N) + x1, dp(2, N) + x2);
         
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
     
    // idx 번째 line 지점에 도달하여 작업 수행하기 까지 걸린시간 
    public static int dp (int line, int idx) {
     
        if (cache1[idx] != 0 && line == 1) {
            return cache1[idx];
        } else if (cache2[idx] != 0 && line == 2) {
            return cache2[idx];
        } else if (idx == 1) {
            if (line == 1){
            return cache1[1] = e1 + S1[1];
            } else {
            return cache2[1] = e2 + S2[1];      // 기저 케이스
            }
        }
         
        if (line == 1) {   
            return cache1[idx] = Math.min(dp(1, idx-1), dp(2, idx-1) + t2[idx-1]) + S1[idx];
        } else { 
            return cache2[idx] = Math.min(dp(2, idx-1), dp(1, idx-1) + t1[idx-1]) + S2[idx];
        }
    }
}