[파이썬] Softeer 연습문제 #10. 복잡한 조립라인2 완벽해설

문제

 

https://softeer.ai/practice/6285

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

 

 

해설

 

 

https://vehiclewithai.tistory.com/14

[파이썬] Softeer 연습문제 #9. 복잡한 조립라인1 완벽해설

 

이 문제는 위에서 해설한 복잡한 조립라인1 문제와 살짝 다르다. 

1번 문제에 "이동 시간은 모두 동일하다." 라는 조건이 붙어 있기에 거리를 위의 문제처럼 하나하나 저장해줄 필요가 없으며, 또한 이동시간이 동일한 탓에 계산이 더욱 간결해진다. 

 

그렇기에 이 문제는 문제가 간결해진 만큼 더욱 효율성이 높은 알고리즘을 요구한다.

 

동적 프로그래밍 문제를 풀기 위해서는 위 글에서 정리된 것 처럼 딱 3가지만 하면 된다.

1. 받아들이는 입력값을 편하게 정리.

2. 규칙 파악.

3. 동적프로그래밍을 통해 값을 계속 갱신.

위의 것들만 하나하나 차근차근히 해주면 된다.

 

 

Step 0. 데이터 받아들일 리스트 준비

import sys

K,N = map(int, sys.stdin.readline().split())
dp = [[10000000 for i in range(K)] for j in range(N)]
dists = []
values = []

 

우선 문제를 풀기에 앞서 데이터를 받아들일 리스트를 준비한다.

 

 

Step 1. 받아들이는 입력값을 편하게 정리

 

그리고 나서 해야할 일은 "들어오는 데이터"를 깔끔하게 정리하는 일이다.

데이터가 들어오는 규칙을 알고, 이를 조금 더 직관적으로 알아보기 위해 위와 같이 깔끔하게 정리한다.

 

# 데이터 깔끔하게 정리
for i in range(N-1):
  data_proc = list(map(int, sys.stdin.readline().split()))
  # 거리 데이터 깔끔하게 정리
  values.append(data_proc[:K])
  dists.append(data_proc[-1])

 

이를 코드로 작성하면 위와 같다.

 

 

Step 2. 규칙 파악

 

그럼 다음으로 동적 프로그래밍 문제의 규칙을 파악하면 되는데,

 

 

규칙을 파악하면 위와 같다. i+1 작업장에서 j번째 조립라인을 갱신할 때, "i번째 작업장에서 동적프로그래밍을 끝낸 값 중 최소값 + 거리값"과 "i번째 작업장 j번째 조립라인" 중의 최소값으로 갱신해준 후, 마지막에 i+1 작업장에서 j번째 조립라인에서 걸리는 작업 시간을 더해주면 끝난다.

 

 

Step 3. 동적프로그래밍

 

# 동적 프로그래밍
for i in range(N-1):
  tmp = min(dp[i])
  for j in range(K):
    dp[i+1][j] = min(dp[i][j], tmp+dists[i])
    dp[i+1][j] += values[i+1][j]

 

이를 코드로 작성하면 위와 같다. 

 

 

코드

 

import sys

K,N = map(int, sys.stdin.readline().split())
dp = [[10000000 for i in range(K)] for j in range(N)]
dists = []
values = []

# 데이터 깔끔하게 정리
for i in range(N-1):
  data_proc = list(map(int, sys.stdin.readline().split()))
  values.append(data_proc[:K])
  dists.append(data_proc[-1])
  
# 마지막 값 저장
values.append(list(map(int, sys.stdin.readline().split())))

# 초기값 세팅
dp[0]=values[0]

# 동적 프로그래밍
for i in range(N-1):
  tmp = min(dp[i])
  for j in range(K):
    dp[i+1][j] = min(dp[i][j], tmp+dists[i])
    dp[i+1][j] += values[i+1][j]

print(min(dp[N-1]))

 

 

결과

 

이 문제를 풀 때 유의해야 될 점은 실행시간이 2초 이하가 되도록 효율적인 알고리즘을 짜야 된다는 점이다. 

 

# 동적 프로그래밍
for i in range(N-1):
  tmp = min(dp[i])
  for j in range(K):
    # dp[i+1][j] = min(dp[i][j], tmp+dists[i])
    for k in range(K):
      if (j==k):
        dp[i+1][j] = min(dp[i+1][j], dp[i][k])
      else:
        dp[i+1][j] = min(dp[i+1][j], tmp+dists[i])
    dp[i+1][j] += values[i+1][j]

 

현재 보이는 위에 있는 코드는 시도하다가 실패한 코드이고,

 

# 동적 프로그래밍
for i in range(N-1):
  tmp = min(dp[i])
  for j in range(K):
    dp[i+1][j] = min(dp[i][j], tmp+dists[i])
    dp[i+1][j] += values[i+1][j]

 

지금 보이는 위에 있는 코드는 성공한 코드이다.

 

원래 3번 돌리는 루프를 "이동시간은 동일하다"라는 규칙을 통해 "i번째 작업장에서의 동적프로그래밍 최소값+이동시간"과 "i번째 작업장에서의 j번째 동적프로그래밍값" 을 비교해주는 방식으로 진행해주면 더욱 간결하게 표현이 가능하고, 이를 통해 해당 문제의 요구조건을 맞출 수 있었다.