반응형
자동차경주대회
-
BOJ) 자동차경주대회알고리즘/백준 2020. 6. 18. 15:05
자동차경주대회 2651번: 자동차경주대회 첫째 줄에 정비소에서 정비하는데 걸리는 총 정비 시간을 출력한다. 둘째 줄에 방문하는 정비소의 개수를 출력한다. 셋째 줄에는 방문하는 정비소의 번호를 한 줄에 차례로 출력하며 정비소 번� www.acmicpc.net 풀이 이 문제는 DP를 활용해서 풀었다. 정비소의 위치와 걸리는 시간을 담을 배열을 각각 선언해서 값을 저장해줬다. 이 때, 출발 지점인 0과 도착 지점인 마지막 위치도 같은 배열에 저장해서 도로의 출발점과 도착점까지 탐색하도록 설정했다. 각 정비소를 들르면서, 이전까지 최대 이동거리인 maxDist안에 있는 정비소를 찾아 걸리는 시간의 최소값을 구했다. 해당 정비소가 최소 시간을 만족하기 때문에, 걸리는 시간을 더해주면서 마지막 도착지점까지 시간이 ..