[BAE/<JOON> 문제풀이] 10217. KCM Travel

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

10217번: KCM Travel

핵심::

DP 메모이제이션

 

풀이::

문제 보자마자 제한 시간 10초길래 흠칫했다.

 

제한된 비용(간선 비용)으로 목적지에 도착하는 최소 거리(시간)를 구하는 문제다.

 

DP[현재 도시][사용한 비용] = 최소 시간

 

최소힙을 사용해 다익스트라를 구현하고 cost 배열에 출발지부터 현재 도착지까지 올 때 사용할 수 있는 가장 적은 비용을 저장한다. 이 때, 다양한 비용이 발생할 수 있는데, 현재 비용보다 많이 사용해서 온 배열의 최솟값도 모두 수정해준다.

현재 도시까지 도달하는데 비용과 시간을 모두 많이 사용했다면 절대 최적값이 될 수 없기 때문이다.

 

그 외에는 새로운 경로를 최소힙에서 출력했을 때 cost 배열에 저장된 최적값보다 안좋은 값이면 리턴 정도만 해서 

3000ms AC를 받았다.

 

의견::

풀고나니까 엄청 쉬워보이는데 되게 안풀렸다. ( 입력받은 값 구조체에 입력할 때 변수 순서 잘못써서 맞왜틀로 3일 날렸다. OTL )

문제 자체도 트릭도 없고 그냥 다익스트란데 플레딱지랑 제한시간 10초보고 쫀 거 같다..

채점 현황보니까 260ms 대 AC 맞은 C++ 풀이랑 1000ms pypy3 풀이가 있다. 어떻게 한걸까,,