https://softeer.ai/practice/info.do?idx=1&eid=403&sw_prbl_sbms_sn=139953

문제

동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다. 두 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Ai (1 ≤ i ≤ N)와 Bi (1 ≤ i ≤ N)로 표시하자. Ai 작업장과 Bi 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다. A 조립 라인의 경우 A1 작업장에서 최초 조립이 시작되고, Ai 작업장에서 작업이 종료되면 바로 Ai+1 작업장에서 작업을 시작할 수 있다.

B 조립 라인도 동일한 방식으로 조립을 진행한다. Ai 작업장에서 Bi+1작업장으로 혹은 Bi 작업장에서 Ai+1작업장으로 반조립 제품의 이동이 가능(이동시간이 추가됨)할 때 자동차 1대의 가장 빠른 조립 시간을 구하여라.

제약조건

1 ≤ N ≤ 103 인 정수
각 작업시간과 이동시간은 105을 넘지 않는 양의 정수

입력형식

첫 번째 줄에 작업장의 수 N이 주어진다. i+1 (1 ≤ i ≤ N-1) 번째 줄에는 Ai 작업장의 작업시간, Bi 작업장의 작업시간, Ai 작업장에서 Bi+1 작업장까지 이동시간, Bi 작업장에서 Ai+1 작업장까지 이동시간이 차례로 주어진다. 마지막 N+1번째 줄에는 AN 작업장과 BN 작업장의 작업시간이 주어진다.

출력형식

첫 번째 줄에 가장 빠른 조립시간을 출력하라.

입력예제1

2
1 3 1 2
10 2

출력예제1

4

Solution

import java.io.*;
import java.util.*;

class Main {
    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());
        int N = Integer.parseInt(st.nextToken());

        int[][] asmLineA = new int[N + 1][2];
        int[][] asmLineB = new int[N + 1][2];

        int[][] DPTable = new int[N + 1][2];
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            asmLineA[i][0] = Integer.parseInt(st.nextToken());
            asmLineB[i][0] = Integer.parseInt(st.nextToken());
            asmLineA[i][1] = Integer.parseInt(st.nextToken());
            asmLineB[i][1] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        asmLineA[N][0] = Integer.parseInt(st.nextToken());
        asmLineB[N][0] = Integer.parseInt(st.nextToken());

        DPTable[1][0] = asmLineA[1][0];
        DPTable[1][1] = asmLineB[1][0];

        for (int i = 2; i <= N; i++) {
            DPTable[i][0] = Math.min(DPTable[i - 1][0], DPTable[i - 1][1] + asmLineB[i - 1][1]) + asmLineA[i][0];
            DPTable[i][1] = Math.min(DPTable[i - 1][1], DPTable[i - 1][0] + asmLineA[i - 1][1]) + asmLineB[i][0];
        }

        bw.write(String.valueOf(Math.min(DPTable[N][0], DPTable[N][1])));
        bw.flush();
    }
}

간단한 Dynamic Programming 문제다.

우선 저장해야 할 데이터는 아래와 같다.

각 라인에서의 작업시간, 옆 라인으로 이동하는 시간. 

그럼 자연스럽게 다음과 같은 점화식이 도출된다.

i > 1인 경우
DP[i][각 라인 번호] = MIN(DP[i-1]각 라인번호, DP[i-1][옆라인] + 해당 라인에서 현재 라인까지 당시 시점에서의 이동시간) + 현재 라인에서의 작업시간

상당히 간단한 문제다. 점화식만 떠오른다면...