[Softeer] python 복잡한 조립라인1

<본 블로그는 Softeer의 코딩테스트 문제를 참고해서 공부하며 작성하였습니다>

https://softeer.ai/practice/info.do?idx=1&eid=404 

Softeer

 

⭐ 문제

언어별 시간/메모리

Python

2초

256MB

문제
동일한 자동차를 생산하는 K개의 조립라인 Li (1 ≤ i ≤ K)가 있다. 한 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Li, j (1 ≤ i ≤ K, 1 ≤ j ≤ N)로 표시하자. 모든 라인의 j번째 작업장은 동일한 작업을 수행하지만 작업 시간은 다를 수 있다. 모든 조립라인은 1번 작업장에서 최초 조립이 시작되며, j번째 작업장에서 작업이 종료되면 바로 j+1번째 작업장에서 작업을 시작할 수 있다. 

Li, j 작업장에서 LK, j+1 (i ≠ K) 작업장으로 이동이 가능(이동시간이 추가됨)할 때, 자동차 1대의 가장 빠른 조립 시간을 구하여라.

제약조건
1 ≤ N ≤ 10^2 인 정수
1 ≤ K ≤ 10^2 인 정수
각 작업시간과 이동시간은 10^5을 넘지 않는 양의 정수

입력형식
첫 번째 줄에 라인의 수 K와 작업장의 수 N이 주어진다.  j+1 (1 ≤ j ≤ N-1) 번째 줄에는 Li, j (1 ≤ i ≤ K) 작업장의 작업시간이 i의 오름차순으로 주어지고, Li, j 작업장에서 LK, j+1 (K ≠ i) 작업장까지 이동시간이 i의 오름차순(i가 동일할 때는 K의 오름차순)으로 주어진다.

출력형식
첫 번째 줄에 가장 빠른 조립시간을 출력하라.

입력예제1
2 2
1 3 1 2
10 2

출력예제1
4

 

✅ Code

# L(i, j) 작업장에서 L(K, j+1) (i ≠ K) 작업장으로 이동이 가능(이동시간이 추가됨)할 때,
# 자동차 1대의 가장 빠른 조립 시간

import sys
input = sys.stdin.readline

# 라인 수, 작업장 수
K, N = map(int, input().split())

dp = []
total_time =[[[0 for i in range(K)] for j in range(K)] for k in range(N)]

for i in range(N-1) :
    # L(i, j) (1 ≤ i ≤ K) 작업장의 작업시간
    work = list(map(int, input().split()))
    # 작업 시간
    dp.append(work[:K])
    cnt = 0

    for j in range(K) :
        for k in range(K) :
            if j == k :
                continue

            total_time[i][j][k] = work[K+cnt]
            cnt += 1

dp.append(list(map(int, input().split())))

for i in range(N-1) :
    for j in range(K) :
        temp = dp[i][j]
        for k in range(K) :
            if j == k :
                continue
            temp = min(temp, dp[i][k] + total_time[i][k][j])
        dp[i+1][j] += temp
print(min(dp[-1]))

 

문제 이해도.. 잘 되지 않는..

https://thflgg133.tistory.com/214

[Softeer/Python] 복잡한 조립라인1 ★★★★☆ - 효과는 굉장했다!

 

 

참고했습니다.. 어렵다