[BOJ][Python] 백준 2056번 - 작업

문제 링크: https://www.acmicpc.net/problem/2056

2056번: 작업

 

 

---

문제 풀이

위상 정렬에 다이나믹 프로그래밍을 이용하는 문제이다. 사실상 웰노운 문제인 1005번의 아이디어를 가져왔다.

상관 관계가 있는 작업의 시간을 가져와 max()로 최댓값을 갱신해줘야 한다. 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 하기 때문이다. dp 테이블을 만들어서 가장 시간이 오래 걸린 것을 출력하면 된다. 이 역시도 max()를 이용하면 된다. 물론 위상 정렬없이 가능한 문제이지만 아이디어가 쉬워서 가져왔다.

 

 

코드