1. 4% WA : 한 노드에서 다른 노드로 가는 노선의 수가 여러 개 임을 놓친 것일 수 있다.
2. 13% TLE : 이 문제는 다익만 쓰면 TLE를 피할 수 없고, DP를 써야 한다. + heapq가 생각보다 느리다. bfs 기반으로 짜서 deq을 이용하면 아닐 것 같지만 시간이 많이 단축된다. 알고리즘적으로 생각해보면 보통은 다익이 빠를텐데, 왜 이렇게 되는지는 잘 모르겠다. 물론 bfs를 돌릴 때 한 루트에서 방문했던 점을 다시 방문하는 것 등은 제외시켜줘야 한다. 4초 -> 1.3초로 급감했다.
3. 30% TLE : (좀 중요한 스포임)
(무언가를) 정렬해보자.
이외 :
dp를 짤 때 맨 처음에는 좀 비효율적이라고 생각할 수 있긴 한데, dp 대신 list + bisect 또는 dict + bisect 로 짜는 것은 상당히 힘든 일이다. 신경써야 할 edge case도 있고, 시간적인 면에서도 그렇게 효율적이지 않았다.
코드에 차이가 전혀 없는 두 제출에서 차이가 좀 심하게 나는 편인 것 같다. (거의 10% 차이나는 case도 있었다.) TLE 나면 운이 안좋았던 것 일 수 있으니 다시 한 번 제출해 보는것도 나쁘지 않은 것 같다.
dgddgd 2년 전 5
1. 4% WA : 한 노드에서 다른 노드로 가는 노선의 수가 여러 개 임을 놓친 것일 수 있다.
2. 13% TLE : 이 문제는 다익만 쓰면 TLE를 피할 수 없고, DP를 써야 한다. + heapq가 생각보다 느리다. bfs 기반으로 짜서 deq을 이용하면 아닐 것 같지만 시간이 많이 단축된다. 알고리즘적으로 생각해보면 보통은 다익이 빠를텐데, 왜 이렇게 되는지는 잘 모르겠다. 물론 bfs를 돌릴 때 한 루트에서 방문했던 점을 다시 방문하는 것 등은 제외시켜줘야 한다. 4초 -> 1.3초로 급감했다.
3. 30% TLE : (좀 중요한 스포임)
(무언가를) 정렬해보자.
이외 :
dp를 짤 때 맨 처음에는 좀 비효율적이라고 생각할 수 있긴 한데, dp 대신 list + bisect 또는 dict + bisect 로 짜는 것은 상당히 힘든 일이다. 신경써야 할 edge case도 있고, 시간적인 면에서도 그렇게 효율적이지 않았다.
코드에 차이가 전혀 없는 두 제출에서 차이가 좀 심하게 나는 편인 것 같다. (거의 10% 차이나는 case도 있었다.) TLE 나면 운이 안좋았던 것 일 수 있으니 다시 한 번 제출해 보는것도 나쁘지 않은 것 같다.