백준20928(걷는 건 귀찮아) - 해결

걷는 건 귀찮아

 

문제

일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 

세상에서 걷는 게 제일 귀찮은 현솔이는 목적지인 M$M$까지 걷지 않고 인력거만을 타면서 이동하고 싶다. 첫 번째 인력거에 타고 있는 현솔이가 목적지까지 가기 위한 인력거의 최소 환승 횟수를 알아 내보자.

 

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 100\,000$, $1 \le M \le 1\,000\,000$)

둘째 줄에 각 지점의 위치 $p_1$, $p_2$, $...$ , $p_N$이 공백으로 구분되어 오름차순으로 주어진다. ($1 \le p_1 \lt p_2 \lt ... \lt p_N \le 1\,000\,000$, $p_1 \le M$)

셋째 줄에 각 인력거꾼의 최대 이동 거리 $x_1$, $x_2$, $...$ , $x_N$이 공백으로 구분되어 순서대로 주어진다. ($1 \le x_i \le 10\,000$)

 

출력

현솔이가 걷지 않고 목적지까지 가기 위한 인력거의 최소 환승 횟수를 출력한다. 만약 도달할 수 없다면, -1을 출력한다.

---

거의 10번 이상 틀렸다.

먼저, 첫 번째 인력거에 타고 있는 이 부분 때문에 초반에 5번 정도 틀리고

그 다음, M 이상의 거리를 갈 때 M 거리를 간다고 설정을 안해줘서

그 다음, $1 \le p_1 \lt p_2 \lt ... \lt p_N \le 1\,000\,000$ 이 부분 나는 M 까지라고 생각을 하고 풀었다.

역시 문제를 꼼꼼히 읽어야한다.

 

풀이 방법은 해당 위치에서 갈 수 있는 거리 중에 다음 갈 수 있는 최대값을 보고 다음 갈 장소를 선정한다.

이 과정을 반복하는 형식

 

import sys

input = sys.stdin.readline

N, M = map(int,input().split())

rickshaw = list(map(int,input().split()))
dist = list(map(int,input().split()))

# 거리가 1000000까지
# 1행은 인력거의 유무
# 2행은 인력거의 거리
road = [[0] * 1000001 for _ in range(2)]

# 인력거의 유무는 0과 1로
for i in range(N):
    road[0][rickshaw[i]] = 1
    road[1][rickshaw[i]] = dist[i]

# 마지막 도착 지점도 도착할 수 있도록
road[0][M] = 1

# 처음 시작
idx = rickshaw[0]
# 다음 인력거 저장
next_idx = rickshaw[0]

# 인력거를 처음 타는 건 빼기위해서
cnt = -1

while 1:
    max_d = 0
    cnt += 1
    # 인력거 거리 중 다음 인력거 선택
    for i in range(1,road[1][idx]+1):
        # 범위내 인력거가 있으면
        if idx + i <= M and road[0][idx + i] == 1:
            # 더 멀리 갈 수 있는지 확인 (=는 뒤에 있는걸 선택하기 위해서)
            if max_d <= idx + i + road[1][idx + i]:
                max_d = idx + i + road[1][idx + i]
                # 더 멀리 갈 수 있어도 M을 초기화 혹시 한번에 갈 수 있는데 못가는 경우가 나올 수 있음.
                if max_d >= M:
                    max_d = M
                # 다음 인력거
                next_idx = idx + i
    # 지금 인력거와 다음 인력거가 같다면 못간다는 걸 의미
    if idx == next_idx:
        break
    
    # 원하는 거리 이상 이라면 끝
    if next_idx >= M:
        idx = M
        break
    # 아니라면 다음 인력거로 이동
    else:
        idx = next_idx

# 끝까지 도착했는지 판단
if idx == M:
    print(cnt)
else:
    print(-1)