[백준] 20928번 걷는 건 귀찮아 (Python)

백준 20928 걷는 건 귀찮아

그리디 알고리즘을 활용한 풀이이다. 접근 방식 자체가 어려운 문제는 아니지만 로직을 깔끔하게 정리하는 데에 시간이 걸렸다. 문제에서 중요한 포인트는 다음과 같다.

1. 현재 도달할 수 있는 위치 중에서 제일 먼 곳을 찾는다.
2. 더 이상 멀리 갈 수 없다면, 제일 먼 곳으로 이동한다.
3. 목표 지점에 도착하지 못했는데 더 이상 갈 수 없다면 -1을 출력한다.

이런 아이디어를 알고리즘으로 정리하면 다음과 같다.

1. 시작하자마자 끝난 경우 예외 처리 (for 문 로직과 충돌하기 때문에 예외 처리를 해줘야 함)
2. tempEnd보다 탐색 중인 시작점이 크다면 닿을 수 없는 경우이기 때문에 종료(위치가 오른차순으로 정렬되어 있기 때문)
3. 탐색 중인 시작점이 현재 위치보다 뒤라면 업데이트(이동하지 않고서는 도달할 수 없기 때문) 단, tempEnd보다 큰 경우는 이미 처리했기 때문에 예외 케이스는 고려하지 않아도 된다.
4. tempEnd 업데이트 후, tempend가 목적지에 도달했는지 확인.

import sys

inp = sys.stdin.readline
n, m = map(int, inp().split())
rickshaws = list(map(int, inp().split()))
dist = list(map(int, inp().split()))
end = dist[0] + rickshaws[0]
tmpEnd = end
cnt = 0
# 시작하자마자 끝난 경우 예외 처리
if end >= m:
    print(0)
    exit(0)

for i in range(1, n):
    s = rickshaws[i]
    if s > tmpEnd:  # 닿을 수 없는 경우
        print(-1)
        break
    if s > end: # 업데이트
        cnt += 1
        end = tmpEnd
    tmpEnd = max(tmpEnd, dist[i] + s)
    if tmpEnd >= m:
        print(cnt + 1)
        break
else:
    print(-1)