[Python][백준] 1446. 지름길

링크🔗

https://www.acmicpc.net/problem/1446

---

🗒️파이썬 코드 풀이

N,D = map(int,input().split(' '))
lst = [list(map(int,input().split(' '))) for _ in range(N)]
lst = sorted(lst)
dp = [i for i in range(D+1)]

k = 0
for i in range(len(dp)):
    dp[i] = min(dp[i-1]+1,dp[i])
    while k<N:
        if i == lst[k][0]:
            if lst[k][1] <= D:
                dp[lst[k][1]] = min(dp[lst[k][1]],dp[lst[k][0]]+lst[k][2])
            k += 1
        else: break

print(dp[D])

 

1. DP로 푸는 문제이다. 

 

2. 0~D(고속도로 길이)까지 dp 리스트를 만들어준다.

 

3. 0~D까지의 반복문을 돌리면서 현재 dp[i] 와, 이전 dp[i-1] + 1 의 dp 값 중 최소 값을 dp[i]로 한다.

(이렇게 하는 이유는 지름길이 적용된 dp 값을 적용시키기 위해서이다.)

 

4. i == lst[k][0]  (차가 지름길 출발지점에 왔을 때) 조건문을 걸고,

 

5. lst[k][1] <= D (목적지 이상으로 간 경우 제외) 하고,

 

6. dp[lst[k][1]] (도착지점) 과  dp[lst[k][0] + lst[k][2] (출발지점 + 지름길 거리) 를 비교

(일반적으로 dp[lst[k][0] + lst[k][2] 가 더 큰게 맞는데, 지름길이 지름길이 아닌 경우와 도착지점이 같은 경우를 걸러준다)

 

ex)
2 10
0  3  1
5  8  1
  
-> DP list = [ 0 ,1,2, 1 ,2, 3 ,4,5, 4 ,5,6]

 

📌  문제 코멘트

dp로 푸는 문제였고, 못 푼 문제이다.

해설을 보고도 이해하는데 시간이 좀 걸렸다.

그리고 1씩 증가하면서 dp를 구현 할지는 정말 몰랐다 ;;

 

확실히 DP 문제를 풀어본 경험이 적어서, 어렵게 느껴졌다. 

값이 계속 누적되고 있다면, DP를 꼭 생각해보자.

 

---

📚문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

예제 입력 1 복사

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

예제 출력 1 복사

70

예제 입력 2 복사

2 100
10 60 40
50 90 20

예제 출력 2 복사

80

예제 입력 3 복사

8 900
0 10 9
20 60 45
80 190 100
50 70 15
160 180 14
140 160 14
420 901 5
450 900 0

예제 출력 3 복사

432