[softeer] 소프티어(파이썬): 조립라인 ★★★

문제

Softeer

- 동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다.

- 두 조립라인에는 각각 N개의 작업장이 있다.

- 각각의 작업장을 Ai (1 ≤ i ≤ N)와 Bi (1 ≤ i ≤ N)로 표시한다.

- Ai 작업장과 Bi 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다.

- Ai 작업장에서 Bi+1 작업장으로 혹은 Bi 작업장에서 Ai+1 작업장으로 반조립 제품의 이동이 가능하다.        (이동시간이 추가됨)

- 작업장의 수가 N일때 1 ≤ N ≤ 10^3 인 정수이다.

- 각 작업시간과 이동시간은 10^5를 넘지 않는 양의 정수이다.

- 이때 자동차 1대의 가장 빠른 조립 시간을 구하는 문제이다.

알고리즘

- 작업장의 수를 입력받는다.

- 반복문을 통해 리스트 형식으로 각 작업장의 시간을 입력받고 리스트 변수에 넣는다.

- 마지막 작업장 시간을 입력받아 리스트 변수에 넣는다.

- 작업장의 수가 1개일 경우에는 마지막 작업장 시간 중 최소인 시간을 출력한다.

- 오로지 a라인에서 작업한 시간과 b라인에서 작업하고 a라인으로 이동한 시간을 비교한다.

- 그중에서 최소 시간을 총 걸린 시간에 넣고 이전 라인에서 걸린 시간에 넣는다.

- b라인도 똑같은 작업을 하고 위 과정을 n-1만큼 반복한다.(마지막 작업장 시간은 따로 계산하기 위해)

- 반복문이 끝나면 각각의 마지막 작업장 시간을 각 라인 시간에서 총 걸린 시간에 더해준다.

- 각 라인에서 총 걸린 시간의 최소를 출력한다.

코드

import sys

n = int(sys.stdin.readline())
line = []
for i in range(n-1):
    line.append(list(map(int, sys.stdin.readline().split())))

# 마지막 작업장 시간
finish = list(map(int, sys.stdin.readline().split()))
# 각 라인에서 총 걸리는 시간
time_a = 0
time_b = 0
# 각 작업장 라인중 이전 라인에서 걸린 시간
work_a = 0
work_b = 0

for i in range(n-1):
    # n이 1일경우에는 작업장이 하나씩이기 때문에 둘중 제일 적은 시간인 경우에만 출력하면 된다.
    if n == 1:
        break
        
    # 오로지 a라인에서 작업한 시간과 b라인에서 작업하고 a라인으로 이동한 시간 비교
    time_a = min(line[i][0] + work_a, line[i][1] + line[i][3] + work_b)
    # 오로지 b라인에서 작업한 시간과 a라인에서 작업하고 b라인으로 이동한 시간 비교
    time_b = min(line[i][1] + work_b, line[i][0] + line[i][2] + work_a)
    # 각 라인에 최소 작업시간을 이전 라인에서 걸린 시간에 넣는다.
    work_a = time_a
    work_b = time_b

# 각각의 마지막 작업장 시간을 각 라인에서 총 걸린 시간에 더해준다.
time_a += finish[0]
time_b += finish[1]

# 각 라인에서 총 걸린 시간의 최소를 출력한다.
print(min(time_a, time_b))

결과

위 코드에서 for문 끝에 print(time_a, time_b)를 작성하면 각 라인의 작업장에서 총 걸리는 시간을 출력 화면과 같이 확인할 수 있다.

<출력화면>

(편의상 작업시간과 이동시간의 단위는 시간으로 하겠다.) 위 출력 화면을 보게 되면 a 라인의 첫 번째 작업장에서 작업을 하고 a 라인의 두 번째 작업장으로 이동한 시간인 1시간이 b 라인의 첫 번째 작업장에서 작업을 하고 a 라인의 두 번째 작업장으로 이동한 시간인 4시간보다 더 최소 시간이기 때문에 a라인에서 걸린 최소 시간은 1시간이 된다.  또, b 라인의 첫 번째 작업장에서 작업을 하고 b 라인의 두 번째 작업장으로 이동한 시간인 3시간보다 a 라인의 첫 번째 작업장에서 작업을 하고 b 라인의 두 번째 작업장으로 이동한 시간인 2시간이 더 최소 시간이기 때문에 b라인에서 걸린 최소 시간은 2시간이 된다. 그리고 마지막 작업장인 두 번째 작업장의 작업 시간을 더해주면 최종적으로 각 라인에서 걸리는 최소 작업시간이 나온다. 따라서 a라인은 11시간이 걸리고 b라인은 4시간이 걸리기 때문에 가장 빠르게 자동차를 조립하는데 걸리는 시간은 4시간이 된다.

따라서 코드를 분석하게 되면 각 라인에서 두 가지 경우(a -> a, b -> a)의 조립 방법 중 최종적으로 걸리는 최소 시간을 도출해내고 그 두 개의 시간 중 최소를 출력하면 가장 빠르게 자동차를 조립하는데 걸리는 시간이 나오게 된다. 이때, 이전 작업장에서 걸린 최소 시간을 포함해야 정확한 답을 찾을 수 있다.

github

junjange/CodingTest