[Softeer/소프티어][level5] 복잡한 조립라인2 (C++)

https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=405&submissionSn=SW_PRBL_SBMS_19088#hold

https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=405&submissionSn=SW_PRBL_SBMS_19088#hold

 

[난이도] level5
[유형] DP

[풀이]
K의 제한이 10^4로 증가하였기 때문에 복잡한 조립라인1 문제처럼 O(N*K^2) 풀이로는 시간내에 해결이 불가능 합니다.
대신 모든 j 작업장에서 다른 라인의 j+1 로 작업장으로 넘어가는데 걸리는 시간이 동일하기 때문에

Bottom-up 방식으로 dp[i][j] (1<=i<=K) 를 계산하기 전에
dp[i][j-1] (1<=i<=K) 중 최솟값 v를 미리 구해주면 아래와 같은 점화식을 세울 수 있습니다.

dp[i][j] = min(v+time[i][j]+mvtime[j-1],dp[i][j-1]+time[i][j]);

case 1) v+time[i][j]+mvtime[j-1] 은 j-1에서 j 작업으로 이동할 때 라인을 바꾼 경우입니다.
이 경우에는 이동간인 mvtime[j-1]을 더해준 것을 알 수 있습니다.

case 2) dp[i][j-1]+time[i][j] 은 라인을 바꾸지 않고 i라인에서 그대로 작업한 경우 입니다. mvtime[j-1]을 더해주지 않았습니다.

case 1에 라인을 바꾸지 않은 케이스 dp[i][j-1]+time[i][j]+mvtime[j-1] 가 포함되어 있습니다. 이때는
mvtime[j-1]을 더하지 않아야 하는데 더해서 문제가 발생할 것 같지만 이 값은 어차피
case 2인 dp[i][j-1]+time[i][j] 값보다 작아 무시되게 되어 문제가 되지 않습니다.

위와 같은 방법으로 O(N*K) 시간에 해결이 가능합니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int K,N,time[10001][101],mvtime[101],dp[10001][101],inf=2e9;
int main(){
    scanf("%d%d",&K,&N);
    for(int j=1;j<=N;j++){
        for(int i=1;i<=K;i++) {
            scanf("%d",&time[i][j]);
            dp[i][j]=inf;
        }
        if(j==N) break;
        scanf("%d",&mvtime[j]);
    }
    for(int j=1;j<=N;j++){
        int v=inf;
        for(int i=1;i<=K;i++) v=min(v,dp[i][j-1]);
        for(int i=1;i<=K;i++) dp[i][j] = min(v+mvtime[j-1]+time[i][j],dp[i][j-1]+time[i][j]);
    }
    int ans=inf;
    for(int i=1;i<=K;i++) ans=min(dp[i][N],ans);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level5/복잡한_조립라인2.cpp