목록지름길 C++ (1)

1일1알

백준 1446번 지름길 C++

D까지 가는 최소 거리를 구하는 문제이다. 역주행은 불가능하다. dp방식으로 해결하였다. 처음에는 거리를 지름길을 고려하지 않고 초기화해주고 지름길들의 도착 위치를 기준으로 정렬한 뒤, 도착 전의 위치들을 검사하면서 도착 위치까지의 최소 거리를 찾아서 지름길을 이용한 최소 거리들을 구하고, 마지막에는 처음부터 D까지 검사하면서 최소 거리를 찾는 방식으로 문제를 해결하였다. 풀고 나서 시작 위치를 기준으로 정렬해도 맞았는데, 이유는 잘 모르겠다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef l..
알고리즘 2021. 12. 8. 12:28
이전 Prev 1 Next 다음