Softeer-연습문제-조립 라인(C++)

문제 링크 : 

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=403

 

문제 개요 : 

A라인과 B라인을 이용해 가장 빠른 생산시간 구하기

 

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv){
        int N;
        cin >> N;
        vector<int>A(N); // A작업시간
        vector<int>B(N); // B작업시간
        vector<int>AtoB(N); // A에서 B로 가는 시간
        vector<int>BtoA(N); // B에서 A로 가는 시간
        for (int i=0;i<N-1;i++){
                cin >> A[i] >> B[i] >> AtoB[i+1] >> BtoA[i+1];
        }
        cin >> A[N-1] >> B[N-1];
        
        for(int i=1;i<N;i++){
                A[i]+=min(A[i-1],B[i-1]+BtoA[i]); // A[i]에서 최솟값
                B[i]+=min(B[i-1],A[i-1]+AtoB[i]); // B[i]에서 최솟값
        }
        cout << min(A[N-1],B[N-1]); // A와 B중 최솟값
return 0;
}

 

문제의 핵심

1) A라인으로 오는 경우는 2가지다. A에서 그대로 오는 경우와 B에서 A로 넘어오는 경우다. 따라서 A[i]로 넘어오는 시간의 최솟값은 A[i-1], (B[i-1]+(B에서 A로 넘어오는 시간)) 둘 중에 더 작은 값이다.

2) B라인도 마찬가지로 B에서 그대로 오는 경우와 A에서 넘어오는 경우 중 더 빠른 것을 택하면 B[i]의 최솟값을 구할 수 있다.

3) 마지막에 A와 B 각각의 최솟값이 나오는데, 이 둘 중에 더 작은 값이 정답이다.