"""
그러면 어떻게 움직일 것이냐의 문제가 남습니다. 이것은 이득이 최대로 되는 경로로 움직이시면 됩니다.
즉, 두 갈래길이 있다고 할 때 왼쪽 길은 +100, 오른쪽 길은 +1 이라면 당연히 이득이 최대로 되는 쪽은 왼쪽이니.
단순하게 왼쪽을 고르시면 됩니다.
이런식으로 현 순간 최대가 되는 경로로 계속해서 움직이시는데 ...
"""
말씀하신대로 매 순간 그리디하게 움직이면 아래 예제에서는 답이 어떻게 나와야 되나요??
제 생각에는 지금 당장은 조금 손해를 보더라도 우회를 해서 나중에 더 큰 이득이 되는 길을 선택하는게 낫다고 봅니다.
(1 -> 2 -> 3 -> 5 -> 6 총 이익 4)

possible 1년 전
해당 문제 스크립트는 굉장히 불친절하다고 생각이 듭니다.
해당 문제를 풀 때 저같은 실수는 안 하셨음에 도움이 될만한 정보를 남깁니다.
문제에서 구하고자하는 정보는 1정점으로부터 N번 정점까지 가는 것입니다.
그 사이에 어떻게 하든 상관이 없고 1 -> ... -> N을 구하시면 됩니다.
그러면 어떻게 움직일 것이냐의 문제가 남습니다. 이것은 이득이 최대로 되는 경로로 움직이시면 됩니다.
즉, 두 갈래길이 있다고 할 때 왼쪽 길은 +100, 오른쪽 길은 +1 이라면 당연히 이득이 최대로 되는 쪽은 왼쪽이니.
단순하게 왼쪽을 고르시면 됩니다.
이런식으로 현 순간 최대가 되는 경로로 계속해서 움직이시는데, 잊지 말아야 하는 것은 최종적으로 N번 정점에 도달해야 하므로, 현재 경로가 N번 정점에 도달하지 못하면 현재 가고 있는 경로는 선택하시면 안됩니다.
다들 파이팅하시길 바랍니다.
참고) 태그는 벨만포드로 돼있는데, 저는 다익스트라로 풀었습니다.