22.08.24. 풀었던 문제

백준 단계별 28 DP와 최단거리 역추적

2618 경찰차 - top-down, bottom-up 둘 다 풀었음.

9019 DSLR

11779 최소비용 - dijkstra 할 때, 같은 edge이지만 cost가 다른 경우.

 ex) from 1 to 2 weight 10 / from 1 to 2 weight 20 이런 경우가 주어지면, 앞의 edge에 의해 update되고, 이게 최소임에도 불구하고 뒤의 edge에 의해 또 update 여부를 보기 때문에 조금 더 시간이 걸린다. 예외 사항 기억하자.

 

11780 플로이드 2 - 역시 역추적은 어렵다.