[BOJ 1005] ACM Craft C++

 

1005번: ACM Craft

 

 

문제풀이

 

이 게임은 건설 순서 규칙에 따라서 건물을 건설해야 한다.

 

위의 예시를 보자.

1번 건물의 건설이 완료된다면 2번과 3번의 건설을 동시에 진행할 수 있다.

그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번 건물의 건설을 시작할 수 있다.

따라서 4번 건물의 건설을 완료하기 위해서는 10초 + 100초 + 10초 = 120초가 소요된다.

120초가 4번 건물을 가장 빨리 지을 때까지 걸리는 최소시간인 것이다.

 

건물 W를 건설완료 하는데 드는 최소 시간을 찾기 위해서 위상 정렬을 해준다.

 

2번 건물을 완성하기 위해서는 1번 건물을 건설 완료해야하므로 총 11초가 걸린다.

3번 건물을 완성하기 위해서는 1번 건물을 건설 완료해야하므로 총 110초가 걸린다.

이 시간을 위상 정렬 시에 DP 배열에 저장해준다.

 

dp[i] = i번 건물을 건설 완료하는데 드는 최소 시간

최소 시간을 찾는 것이지만 선행 건물들이 모두 건설완료가 되어야하므로 최댓값을 찾는 것이다.

 

처음에 선행 정점을 가지지 않는 정점을 큐에 삽입할 때는 dp[i] = t[i]로 초기화해준다.

그리고 나서 다음 순서를 진행할 때 앞순서 건물 건설시간 + 현재 건물 건설시간 이 최대인 것을 저장해주면 해당 건물을 건설완료 하는데 드는 최소 시간을 구할 수 있다.

 

 

C++ 코드