park94128   1년 전

코테 공부중이라서 정답 코드는 일부러 보지 않고 힌트와 방법만 봤으나 아무리 해도 시간 초과에 걸리네요. 문제점을 찾아주시면 감사하겠습니다.

jyunni   1년 전

현재 코드에서 유일하게 호출 횟수를 줄여주는 분기는 if(중복방문 && 적거나 같은 비용) 밖에 없어서 그렇습니다. 하지만 이것만으로는 부족합니다.  
 
적은 비용으로 어떤 정점을 재방문하는 경우, 앞으로 (visitBit를 모두 채우기 위해) 남은 m개의 정점에 대해 또 탐색을 해야합니다.  
간선의 비용은 그대로이니, 남은 정점들 역시 낮은 비용으로 재방문하게 될것이고, 다시 처음으로 돌아와서...  
즉, 더 효율적인 방법이 필요합니다.  

힌트를 남기자면, 남은 m개의 정점에 대해서는 어떤 경로로 가는지는 궁금하지 않습니다, 그대신 얼마나 싸게 갈수 있는지 누군가 계산해둔게 있다면 어떨까요?

댓글을 작성하려면 로그인해야 합니다.