BOJ 24888 - 노트 조각

BOJ 24888 - 노트 조각

항상 최단 경로로 가야 하는게 힌트이다.

$(d, a)$ 를 $i$ 번 정점까지의 최단 경로와 최대 먹을 수 있는 노트 수라고 한다면 $d$ 는 작을수록 $a$ 는 클수록 좋다는 것으로 다익스트라를 돌릴 수 있고, 역추적 하면 된다.