[백준] 1446 - 지름길

백준 1446번 지름길

 

➡️문제 링크 : https://www.acmicpc.net/problem/1446

 

 

요즘 dp 문제를 많이 풀고 있어서 문제를 보자마자 dp인 것 같은데..? 라는 생각을 하긴 했지만 10000이라는 큰 수에 dp일리는 없다고 생각했다. 그러나 아무리 머리를 쥐어짜도 dp밖에는 답이 없는 것 같아서 슬며시 '알고리즘 분류'를 내려봤고(최근에 자주 내려보고 있다...ㅠㅠ 실버를 더 다져야 할 듯 하다) 아니나 다를까 dp가 맞았다. 

 

dp로 문제를 풀 수 있다고 생각한 이유는 dp밖에는 이 모든 경우의 수(?)를 다룰 방법이 없어보여서였다. 수가 작다 해도 최대 12개의 지름길을 o,x로 모든 경우의 수를 짐작하기에는 128MB는 적어 보였고, min 값을 계속 갱신하는 방법으로 이 문제를 푸는 게 최선일 거라고 직감했다.

먼저 dp를 시작점부터 각 i 지점까지의 본래 거리로 초기화했다. 지름길을 지나면, 도착위치부터 끝까지 시작점부터 i 위치까지의 거리를 갱신해줘야 했다. 

만약 이전에 80 - 190 지름길을 갔는데 이후 140 - 160 지름길을 만나면 겹치는 거 아닌가..? 라고 생각했지만 80부터 189까지는 똑같은 거리이기 때문에 140과 160과는 무관하게 따로 계산될 수 있고, 이후 190 이상부터는 첫 번째 지름길을 갔을 때와 두 번째 지름길을 갔을 때, 시작점부터 i 점까지의 거리를 min() 함수로 비교하기 때문에 겹치지 않았다.

다만, 지름길 리스트를 시작점 순으로 정렬해줘야 했다. 문제의 예제 3에서는 160 - 180 이후에 140 - 160 이 나온다. 만약 첫 번째 지름길 이후에 두 번째 지름길로 리스트를 갱신한다면 두 지름길을 한 번에 건널 수 있음에도 하나씩만 건너도록 비교되어 버린다. 따라서 반드시 시작점 순으로 정렬 후 각 지름길을 건너는 게 나을지 판단해줘야 한다. 

 

코드는 다음과 같다. 

 

# DP

import sys

input = sys.stdin.readline

n,d=map(int, input().split(' '))

dp=[i for i in range(d+1)]

lst=[list(map(int,input().split(' '))) for _ in range(n)]
lst=sorted(lst,key=lambda x : (x[0]))

for i in range(n):
    s,e,dist=lst[i][0],lst[i][1],lst[i][2]
    if not (0<=s<d) or not (0<e<=d):
        continue
    if dp[e]-dp[s]>dist:
        for j in range(e,d+1):
            dp[j]=min(dp[j], dp[s]+dist+(j-e))

print(dp[d])