[Algorithm] Softeer 조립라인 - Lv.3 (Python)

[ Softeer 연습문제 - 조립라인 ]

Softeer - 현대자동차그룹 SW인재확보플랫폼

• 문제명 : 조립라인 (Level.3)
• 사용언어 : Python
• 사용 알고리즘 : DP (Dynamic Programming)

---

  문제 

동일한 자동차를 생산하는 2개의 조립 라인 A와 B가 있다. 두 조립라인에는 각각 N개의 작업장이 있다. 각각의 작업장을 Ai (1 ≤ i ≤ N)와 Bi (1 ≤ i ≤ N)로 표시하자. Ai 작업장과 Bi 작업장은 동일한 작업을 수행하지만 작업시간은 다를 수 있다. A 조립 라인의 경우 A1 작업장에서 최초 조립이 시작되고, Ai 작업장에서 작업이 종료되면 바로 Ai+1 작업장에서 작업을 시작할 수 있다.
B 조립 라인도 동일한 방식으로 조립을 진행한다. Ai 작업장에서 Bi+1 작업장으로 혹은 Bi 작업장에서 Ai+1 작업장으로 반조립 제품의 이동이 가능(이동시간이 추가됨)할 때 자동차 1대의 가장 빠른 조립 시간을 구하여라.

 

 

 

  문제 풀이 & 알고리즘

:  2*2=4, 4가지의 경우가 나오는 테스트 케이스는 이해가 되었지만 그 이상의 케이스는 이해하기 어려웠다. 

입력 조건에 따른 전체 케이스를 이해하기 위해 메모장을 꺼내 들고 이해하려고 노력했다... T_T

결과에서 원하는 최적의 조립시간을 구하기 위해서는 시간 복잡도를 O(N)으로 낮추는 것이 핵심이었다.

 

점화식을 세우고 for문을 돌려 각각의 작업장에서 최소 조립 시간을 저장하면서 진행하는 방법으로 구현했다.

점화식에서는 (a→a , b→a) a로 오는 두가지의 케이스를 따져줘야된다.

 

 

※  A라인에서 i번째 작업장까지의 최소 조립 시간

   : finish[0][i] = min(finish[0][i-1] , finish[1][i-1] + switch[1][i-1])  + work[0][i]

 

- switch[1][i-1] : B라인의 i-1번째 작업장에서 A라인의 i번째 작업장으로 이동하는 시간.

- work[0][i] : A라인의 i번째 작업장에서의 작업시간

 

 

 
  실행 코드

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()))
# 총 걸리는 시간
total_time_a = 0
total_time_b = 0
# 이전 라인에서 걸린 시간
before_work_a = 0
before_work_b = 0

for i in range(n-1):
    
    if n == 1:
        break
        
    # a->a, b->a 두 시간 비교
    total_time_a = min(line[i][0] + before_work_a, line[i][1] + line[i][3] + before_work_b)
    # b->b, a->b 두 시간 비교
    total_time_b = min(line[i][1] + before_work_b, line[i][0] + line[i][2] + before_work_a)
    
    before_work_a = total_time_a
    before_work_b = total_time_b
    

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

# 총 걸린 시간의 최소를 출력.
print(min(total_time_a, total_time_b))

 

 
▼ 결과 ▼

 

 

여러 번 방향을 바꿔가며 시도 끝에 결국 성공은 해냈지만,, 

처음에 원하던 배열의 방식으로 성공은 못했다...ㅜㅜ 담에 다시 배열 도전.. C++로 풀어봐야겠당..... 쥬륵..