99클럽 코테 스터디 27일차 (BOJ 1446 지름길)

오늘의 문제: BOJ 1446(지름길)

문제 설명

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

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

 

문제풀이

도착지점 까지 갈수 있는 방법은 총 2가지이다. 

1. 고속도로를 타고 그냥 가기

2. 지름길을 사용해서 가기

위의 방법을 고려해서 dp에 최소값을 기록하면서 도착지점까지 가는 최소값을 기록해주면 된다.

주의 사항으로는 되돌아오는 것이 불가능하기 때문에 지름길의 끝점이 도착 지점을 지나치면 지름길을 사용할 수 없다.

# 입력받기
n, end = map(int, input().split())
short_load = [tuple(map(int, input().split())) for _ in range(n)]

# 지름길 시작점 기준으로 정렬
short_load.sort()

# 무한대 값 설정
INF = float('inf')
dp = [INF] * (end + 1)
dp[0] = 0  # 시작점 비용은 0

# dp 갱신
for i in range(end + 1):
    # 일반 도로로 이동
    if i > 0:
        dp[i] = min(dp[i], dp[i - 1] + 1)
    
    # 지름길 고려
    for a, b, cost in short_load:
        if i == a and b <= end:
            dp[b] = min(dp[b], dp[a] + cost)

# 결과 출력
print(dp[end])