백준 1005 - ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

그래프 탐색과 동적 프로그래밍 기법을 활용해 풀었다.

 

각 타워의 개별 건설 비용을 저장할 1차원 cost 배열,

타워 간의 건설 순서를 저장할 2차원 order 배열,

DP의 optimal substructure 생성을 위한 1차원 sum 배열,

그래프 탐색을 위한 1차원 visited 배열

 

총 4가지 배열을 사용했다.

 

optimal substructure는 다음과 같이 설계한다.

i번째 건물 Di를 짓는 개별 시간을 Ti, 게임 시작부터 Di 건설 완료까지 걸리는 시간을 Si라고 하자.

Di를 짓기 시작하려면 Di 건설을 위해 요구되는 모든 건물이 지어진 상태여야 한다.

따라서 order[j][i]에 값이 존재하는 모든 건물 Dj에 대하여 Si = max(Sj + Ti)이다.

 

문제 해결 과정은 아래와 같다.

 

건설비용과 건설순서를 입력받아 저장한다.

 

건물 전체 수 n에 대해 Si = max(Sj + Ti)를 이용해 sum 배열을 채운다.

 

이때 i < j일 경우 Sj의 값이 아직 계산되지 않은 문제가 발생한다. ex) 4 -> 1

 

따라서 그래프 탐색 방식을 적용해, visited 배열을 확인해 Sj가 아직 계산되지 않았다면

함수의 재귀호출을 통해 j로 이동하고, 계산을 마친 건물은 visited의 값을 1로 바꾼다.

 

표를 다 채우고 나면 비용을 계산할 건물의 번호를 입력받아 이미 완성한 배열에서 값을 반환한다.

 

배운 내용 : 그래프 탐색 복습(재귀호출 또는 스택을 기반으로 해야함)