편집 시간: 2022년 3월 4일 오후 2:39
코드
Algorithm/1005.py at main · Junroot/Algorithm
풀이
내 풀이
건물 사이의 건축 선후 관계가 존재하기 때문에 위상 정렬을 사용하면 된다고 생각했다. 기본적으로 위상 정렬로 문제를 푸는데 다음 현재까지의 건축 시간을 자신보다 한 단계 앞의 건물 중에 가장 오래 걸린 건물을 기준으로 ㅅ계산을 해야되므로 이를 저장하는 리스트를 하나 만들었다.(dp)
마지막에 목적지 건물에 도착하면 (목적지 건물에 도착하는데 걸리는 시간) + (목적지 건물을 짓는데 걸리는 시간)을 출력하면 된다.
다른 사람 풀이
다른 사람 풀이를 보니 탑다운 방식의 dp를 이용하는 방법도 있었다.
- f(x): x 건물을 짓는데 필요한 시간
f(x) = max(f(k)) + build_time[x] | {k | k는 x번 빌딩이 짓기전에 지어야되는 빌딩 번호}