❗문제❗
🤔생각의 흐름
- N의 최대값이 12이므로 완전탐색, 백트랙킹도 가능하겠다.
- 선택하는 것에 따라서 이후의 값들이 영향을 받는 것 같은데, 패턴을 한 번 찾아볼까?
- 도착 위치가 D보다 크거나 지름길을 이용했을 때 더 오래걸리는 입력들은 무시하고 생각해보자.
- 출발위치와 도착위치가 같은 입력들은 그 중에서 지름길의 길이가 짧은 입력만 받아들이자.
- 정리된 입력값들을 쭉 나열해보니, 이전 인덱스의 값을 이용하여서 이후 인덱스의 값을 결정하네? DP로 접근해야겠다.
🧻풀이
- 딕셔너리를 이용하여 (출발점, 도착점)을 key로 하고 지름길 길이를 value로 입력받기.
1.1 도착위치 - 출발위치 <= 지름길 입력 제외
1.2 도착위치 > D 입력 제외
1.3 딕셔너리에 값을 넣을 때 같은 key가 존재한다면, 지름길 길이가 작은 값으로 업데이트 - 딕셔너리에서 출발점과 도착점을 추출하여 중복없는 리스트로 만들기
2.1 출발점인 0과 도착점인 D는 항상 존재해야 하므로, 리스트에 추가 - 위에서 만든 리스트와 같은 크기의 리스트를 하나 생성
- 지점이 저장된 리스트의 값을 차례대로 읽으며, 생성한 리스트의 값을 업데이트한다.
4.1 이전 지점의 값 + (현재 지점 위치 - 이전 지점 위치)와 현재 지점을 도착지점으로 하는 값들을 딕셔너리에서 찾아서 모두 비교 한 후 가장 작은 값을 리스트에 업데이트 한다.
말이 어려우니, 예제 입력 3번을 기준으로 설명해보겠다.
N = 8, D = 900
(0, 10) : 9
(80, 190): 100
(50, 70): 15
(160, 180): 14
(140, 160): 14
(450, 900): 0
이 값들만 입력으로 받게 된다.
그리고, 출발점과 도착점으로 리스트를 만든다.
[0, 10, 50, 70, 80, 140, 160, 180, 190, 450, 900]
그리고, 새로 리스트를 하나 생성하여 지점까지의 최소 값을 담는다.
예를 들어, 70까지 가기 위해서 얼마만큼의 거리를 이동해야 하는가를 보자.
(0, 70) + 0, (10, 70) + 10에 해당하는 값, (50, 70) + 50에 해당하는 값, 70-50 + 50에 해당하는 값 이 값들을 비교하여 가장 작은 값을 새로운 리스트의 70에 해당하는 3번째 index에 값을 업데이트 한다.
(딕셔너리에 (0, 70), (10, 70), (50, 70) 값 중 존재하지 않는 것들은 계산하지 않는다. 70-50 + 50에 해당하는 값은 무조건 존재하기 때문에, 딕셔너리에 모두다 없다면, 50이 가지고 있는 값에서 70-50을 더해준 값이 업데이트 된다.)
이렇게 값을 끝까지 업데이트하면
[0, 9, 49, 64, 74, 134, 148, 162, 172, 432, 432]가 된다.
리스트의 마지막 값이 정답이 된다.
📔후기
문제 이름부터 지름길이었고, 최단 거리를 찾는 문제여서 다익스트라나 BFS를 썼으면 쉽게 풀었을 것 같다. 그래프로 생각하지 못하여서 DP를 이용해서 풀었는데, 괜히 어렵게 생각 한 것 같다. 최단 거리를 찾는 문제에 익숙해질 필요를 느꼈다.
