[DP(Dynamic Programming)] 백준-14767 Flow Shop(Python)

백준-14767 : Flow Shop

https://www.acmicpc.net/problem/14767

14767번: Flow Shop

 

문제

• n개의 스웨터 주문과, m개의 공정을 과정을 입력 받는다.
• 각 공정마다 기계는 한개씩 존재하고 동시에 사용은 불가능하다.
• 먼저 들어온 주문 부터 제작을 시작하고 앞에 공정을 거처야만 다음 공정을 진행할수있다.
• 해당 공정의 기계가 사용중이라면 공정이 끝난이후에 작업이 가능하다.

풀의

• 각 공정 마다 최종 사용 상태의 DP 테이블을 생성한다.
• DP 테이블을 확인인하며
  • 바로 기계 가능하면 해당 공정 작업후 기계 최종 사용시간을 수정한다.
  • 바로 공정이 가능하지 않다면 공정을 대기한 이후에 기계를 사용후 기계 최종 사용 시간을 수정한다.

 

코드 (Python)

import sys

def input():
    return sys.stdin.readline().rstrip()

n, m = map(int, input().split())

swather_list = [list(map(int, input().split(" "))) for _ in range(n)]

dp = [0] * m
result_list = [0] * n

for i in range(n):
    for j in range(m):
        # 줄을 서고 이용
        if (dp[j] > result_list[i]):
            dp[j] += swather_list[i][j]
        # 바로 사용가능
        else:
            dp[j] = swather_list[i][j]+result_list[i]
        result_list[i] = dp[j]

print(*result_list)