[백준 / BOJ] 1005 ACM Craft

문제

출처 : www.acmicpc.net/problem/1005

1005번: ACM Craft

내가 원하는 건물을 건설할때 걸리는 최소 시간을 출력하는 문제다.

 

 

풀이

완전탐색으로 풀경우

N <= 1000, K <= 100000 이라서

1억 * T 만큼 반복해서 터진다.

 

한번 탐색한 곳을 탐색하지 않도록 해줘야하는데,

 

check배열을 만들어서, 이미 탐색한 경로라면 더이상 가지않고, 해당 위치의 건물을 만든시간을 리턴해줬다.

 

1. 경로를 역순으로 저장한다

(어차피 역순으로 올라가면서 더해줄것이므로 역순으로 해줘도됨)

이렇게 저장해주면 전 위치에 어떤건물을 지어야 현재위치의 건물을 지어야할지 알수있음

예를들어, 예제의 경우

4 -> 2

4 -> 3

이렇게 저장이 될건데, 4번건물을 짓기위해선 4번에 연결된 건물들을 모두 지어야한다(2번과 3번)라는 뜻

 

2. 끝까지 탐색하며 건물을 지을때마다 check배열을 업데이트 해준다. (바텀업으로 구현함) 

check배열을 업데이트할때, 전 위치의 건물들중 최댓값을 뽑아서 업데이트 해줘야함

이때 이미 전 단계의 check배열이 업데이트 되어있는 상황이라면 더 이상 들어가지않고, 전단계의 check배열값을 가져와서 계산한다.

(바로 전 위치의 건물들은 동시에 짓기시작할수있고 이때, 걸리는 시간은 항상 최댓값임)

 

이렇게 하면, T * N번 반복으로 통과됨

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1005%20ACM%20Craft/main.cpp

devxb/JJUNalgo