[SWEA/Python] 5208. 전기버스2

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 현재 정류장에서 충전한다면 최대 어디까지 갈 수 있는지를 미리 계산해서 max_station 리스트에 저장한다.
   인덱스를 맞춰주기 위해 0번은 비워놓았다.
2. 타겟은 원하는 도착 지점이다.
   max_station을 순회하면서 타겟까지 도착할 수 있는 정류장이 있다면,
   그 정류장을 타겟으로 다시 max_station을 순회하며 해당 정류장까지 도착할 수 있는 정류장을 찾는다.
3. 위의 과정을 반복하며 카운팅한다.

 

📌 코드

import sys
sys.stdin = open('input.txt')

T = int(input())

for t in range(1, T+1):
    temp = list(map(int, input().split()))
    N = temp[0]
    battery = [0] + temp[1:]

    # 현재 정류장에서 충전해서 최대 어디까지 갈 수 있는지 저장
    max_station = [0 for _ in range(N)]
    for i in range(N):
        max_station[i] = i + battery[i]

    cnt = -1 # 1번 정류장에서 장착은 교환횟수에서 제외
    target = N
    j = 1
    while target > 1:
        if max_station[j] >= target:
            cnt += 1
            target = j
            j = 1
        else:
            j += 1
    
    print('#{} {}'.format(t, cnt))