백준 2056 작업 파이썬 풀이

난이도 : 골드4

풀이일 : 05055

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

2056번: 작업

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

# 입력 시, temp 리스트 활용으로 project 삽입
# 새 누적 시간과 현재 누적 시간을 비교, 큰 값 저장
# 선행 작업 완료할 때 마다 count - 1
# count 0 되면 작업 시작 -> queue 추가
# 최종 누적 시간 중 가장 큰 값 출력

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
time = [0] * N
count = [0] * N
project = [[] for _ in range(N)]
total = [0] * N

for i in range(N):
    t, c, *temp = map(int, sys.stdin.readline().split())
    time[i], count[i] = t, c
    for p in temp:
        project[p-1].append(i)

queue = deque()
for i in range(N):
    if not count[i]:
        queue.append(i)
        total[i] = time[i]

while queue:
    x = queue.popleft()
    for y in project[x]:
        count[y] -= 1
        total[y] = max(total[x] + time[y], total[y])
        if not count[y]:
            queue.append(y)

print(max(total))

코드 구성

• time : 작업 개별 수행 시간
• count : 선행 작업 수
• project : 선행 작업
• total : 누적 시간
• 입력 시, temp 리스트 활용으로 project 삽입
• 새 누적 시간과 현재 누적 시간을 비교, 큰 값 저장
• 선행 작업 완료할 때 마다 count - 1
• count 0 되면 작업 시작 -> queue 추가
• 최종 누적 시간 중 가장 큰 값 출력

---

느낀점

며칠 째 비슷한 로직을 풀고 있어서 쉽고 재밌다. 이런 유형 다 풀어봐야지

입력 받을 때, 패킹을 사용해서 리스트에 넣는 작업이 특히 재밌었다.