사용자 도구

사이트 도구


ps:problems:boj:2056

작업

ps
링크acmicpc.net/…
출처BOJ
문제 번호2056
문제명작업
레벨골드 4
분류

위상 정렬

시간복잡도O(n*m)
인풋사이즈n<=10000, m<=100
사용한 언어Python
제출기록29340KB / 256ms
최고기록228ms
해결날짜2020/11/25

풀이

  • 위상 정렬 (Topological Sorting)의 대표적인 응용인 임계 경로의 길이를 구하는 문제.
  • 원래는 위상 정렬을 수행하면서 길이를 계산하는 것이 일반적인 방법인데, 이 문제에서는 주어지는 데이터는 이미 위상정렬이 되어있는 상태이다. 따라서 위상정렬된 결과에서 임계 경로만 계산하면 된다.
  • 계산식은
    • n번 작업이 끝날 때까지 필요한 총 시간 = (n번 작업의 선행 작업들중 가장 늦게 끝나는 시간) + n번 작업의 소요시간

코드

"""Solution code for "BOJ Q2056. 작업".

- Problem link: https://www.acmicpc.net/problem/2056
- Solution link: http://www.teferi.net/ps/problems/boj/2056
"""

import sys


def main():
    N = int(sys.stdin.readline())
    complete_times = [0] * (N + 1)
    for i in range(N):
        t, _, *dependencies = [int(x) for x in sys.stdin.readline().split()]
        complete_times[i + 1] = t
        if dependencies:
            complete_times[i + 1] += max([complete_times[work]
                                          for work in dependencies])
    print(max(complete_times))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
W R B P L
 
ps/problems/boj/2056.txt · 마지막으로 수정됨: 2020/12/03 15:01 저자 teferi