Softeer-연습문제-복잡한 조립라인2(C++)

문제 링크 : 

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

 

문제 개요 : 

다양한 조립라인들을 이용해 가장 빠른 생산시간 구하기

 

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

using namespace std;

int main(int argc, char** argv)
{
        int N,K;
        cin >> K >> N;
        vector<vector<int>>map(N,vector<int>(K)); // 2차원 배열에 저장
        vector<int>move(N); // 다른 조립라인의 다음 작업장 이동시간
        for(int i=0;i<N-1;i++){
                for(int j=0;j<K;j++){
                        cin >> map[i][j]; // j조립라인 i작업장
                }
                cin >> move[i]; // i작업장 -> i+1작업장
        }
        for(int i=0;i<K;i++){
                cin >> map[N-1][i]; // 각 조립라인의 마지막 작업장
        }

        // 첫 번째 작업장에서의 최솟값 구하기
        int mn=map[0][0];
        for(int i=1;i<K;i++){
                mn=min(mn,map[0][i]);
        }

        // 각 작업장에서의 최솟값 구하기
        int n_mn;
        for(int i=1;i<N;i++){
                n_mn=987654321;
                for(int j=0;j<K;j++){
                        map[i][j]+=min(map[i-1][j],mn+move[i-1]); // j조립라인 i작업장의 최솟값
                        n_mn=min(n_mn,map[i][j]); // 현재 작업장의 최솟값 구하기
                }
                mn=n_mn; // 현재 작업장에서의 최솟값을 mn에 대입
        }

        int tmp=map[N-1][0];
        for(int i=1;i<K;i++){
                tmp = min(tmp,map[N-1][i]);
        }
        cout << tmp;

 return 0;
}

 

주의해야 할 요소들

1) 복잡한 조립라인1처럼 풀면 시간초과가 나온다.

2) j조립라인 i작업장으로 오는 경우는 2가지다. 같은 j라인 이전 작업장에서 오거나 다른 라인 이전 작업장에서 오는 경우 이렇게 2가지다.

3) 특히 다른 라인 이전 작업장에서 오는 경우, 모든 이동시간이 같으므로 (이전 작업장에서의 최솟값 + 이동시간) 하나만 고려해주면 된다. 필자는 이전 작업장에서의 최솟값을 mn에 저장했고, 현재 작업장에서의 최솟값을 n_mn에 저장하여 풀이했다.