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

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=404&sw_prbl_sbms_sn=18720

Softeer

 

 

[난이도] level4
[유형] DP

[풀이]
다이나믹 프로그래밍을 이용해서 해결할 수 있습니다.
time[k][n] : k번 라인의 n번 작업장의 작업시간
mvtime[k][n][i] (i!=k) : k번 라인의 n번 작업장에서 i번 라인의 n+1번 라인으로 옮길때의 시간
dp[k][n] : k번 라인의 n번 작업부터 시작했을 때 N번 작업을 끝날때까지 걸리는 최소 시간

Top-Down DP를 이용하였으므로
sol(k,n) 은 dp[k][n]을 저장하며 리턴합니다.

점화식은 아래와 같습니다.
for(int i=1;i<=K;i++) dp[k][n]=min(dp[k][n],sol(i,n+1)+time[k][n]+mvtime[k][n][i]);
현재 작업 라인 k에서 1~K번 라인으로 넘어갈 수 있으며 그때의 이동시간인 mvtime을 더해주는 것을 알 수 있습니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int K,N,time[101][101],mvtime[101][101][101],dp[101][101],inf=2e9;
int sol(int k,int n){
    if(n==N) return time[k][n];
    int& ret = dp[k][n];
    if(ret!=-1) return ret;
    ret=inf;
    for(int i=1;i<=K;i++) ret=min(ret,sol(i,n+1)+time[k][n]+mvtime[k][n][i]);
    return ret;
}
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]);
        if(j==N) break;
        for(int i=1;i<=K;i++)
            for(int k=1;k<=K;k++)
                if(i!=k) scanf("%d",&mvtime[i][j][k]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

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