kth2642   1일 전

DP와 DFS를 이용해 코딩해봤습니다 

take_time에 건물들을 짓는 시간을 저장하고 

route에 각 건물을 짓기 전에 지어야하는 건물들을 건물 번호순으로 저장했습니다 

DP 풀이를 위한 저장 공간으로 cache 리스트를 만들었구요 

min_time 함수에서 cache에 짓는 시간이 저장되어있으면 계산없이 그대로 그걸 가져오고 

저장되어있지 않은 경우 재귀를 돌려서 짓는 시간을 가져오는 식으로 했는데..

54%에서 시간 초과가 나네요 ㅠㅠ

입력받은 케이스에서 K가 압도적으로 커서 사실 N은 거의 시간에 영향을 안주는 거 같은데 

그래서 16~18번 줄이 문제가 아닌가 의심되긴 하는데..

어떻게 고치면 될 지 잘 모르겠네요..
코드 지적 부탁드립니다!

paaapaaa   20시간 전

입력과정에서 시간이 많이 소요됩니다.

제한사항을 확인해봐도 입력이 10만개가 훌쩍 넘어가기 때문에

input()을 사용해서 입력 받는 것은 시간이 오래걸립니다.

실제로 제가 입력 부분만 수정해서 채점돌려봐도 통과가 됩니다.

https://www.acmicpc.net/blog/v...

참고하시면 될것같습니다

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