[Softeer/소프티어] 조립라인 - 자바[Java]

https://softeer.ai/practice/6287

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

처음에는 BFS를 통해 가장 빠른 조립시간을 구하려 했다. 하지만 BFS로 수행할 시 메모리 초과가 발생했다.

풀이방법에 대해 더 생각해보았더니 DP를 사용하여 해당 작업장까지의 최소 조립시간을 구하는 방식으로 풀었다.

// 0 <= i <= n-1
dp[i][0]: A 조립라인의 i번째 작업장까지의 최소 조립시간
dp[i][1]: B 조립라인의 i번째 작업장까지의 최소 조립시간

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        int[] b = new int[n];
        int[] atoB = new int[n];
        int[] btoA = new int[n];

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
            atoB[i] = Integer.parseInt(st.nextToken());
            btoA[i] = Integer.parseInt(st.nextToken());
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        a[n-1] = Integer.parseInt(st.nextToken());
        b[n-1] = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n][2]; // 해당 작업장까지의 최소 조립시간
        dp[0][0] = a[0];
        dp[0][1] = b[0];
        
        for (int i = 0; i < n-1; i++) {
            dp[i+1][0] = Math.min(dp[i][0], dp[i][1] + btoA[i]);
            dp[i+1][0] += a[i+1];

            dp[i+1][1] = Math.min(dp[i][1], dp[i][0] + atoB[i]);
            dp[i+1][1] += b[i+1];
        }
        
        System.out.println(Math.min(dp[n-1][0], dp[n-1][1]));
    }
}