[BOJ]1516번: 게임 개발

www.acmicpc.net/problem/1516

---

건물 짓는 선후 관계가 있기 때문에 위상정렬로 해결할 수 있습니다.

 

1. 선후 관계를 만족하는 임의의 위상 정렬 순서 구하기

2. 1번에서 구한 순서를 바탕으로 실제 BuildTime 구하기

 

아래와 같은 관계가 성립합니다.

 

현재 빌딩을 짓는데 실제 걸리는 시간

= 현재 빌딩을 짓는데 원래 걸리는 시간 + 먼저 지어야 하는 건물을 짓는데 실제 걸리는 시간 중 최댓값

 

realBuildTime[now] = max(realBuildTime[preBuilding]) + buildTime[now]

---

코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ1516.cc