dgddgd   2년 전

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 나면 운이 안좋았던 것 일 수 있으니 다시 한 번 제출해 보는것도 나쁘지 않은 것 같다.

askk27   2년 전

3번 을 참고해서 무언가 정렬하니 정답이 도출되네요.. 근대 정렬이 어떤 역할을 할까요?

not_strober   1년 전

정말 감사합니다. 특히

'(무언가를) 정렬해보자.'

여기서 소름이 돋았네요. 이런 방법이 있다니..

ojs8879   1년 전

참. 다익에서 dp 안쓰고 pq에다 다 쑤셔박는 버릇 고쳐야 하는데...

정렬은 시행할 경우 필요 이상으로 dp에 접근하는 횟수가 줄어들어서 그런 거 같네요.

u, v가 같고 cost만 다른 경우도 고려해 볼 법 하네요....

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