문제 출처 : [SWEA] 4831 전기버스
learn -> course -> programming intermediate -> list1 -> 전기버스

문제

A도시는 전기버스를 운행하려고 한다. 전기버스는 한번 충전으로 이동할 수 있는 정류장 수가 정해져 있어서, 중간에 충전기가 설치된 정류장을 만들기로 했다.

버스는 0번에서 출발해 종점인 N번 정류장까지 이동하고, 한번 충전으로 최대한 이동할 수 있는 정류장 수 K가 정해져 있다.

충전기가 설치된 M개의 정류장 번호가 주어질 때, 최소한 몇 번의 충전을 해야 종점에 도착할 수 있는지 출력하는 프로그램을 만드시오.

만약 충전기 설치가 잘못되어 종점에 도착할 수 없는 경우는 0을 출력한다. 출발지에는 항상 충전기가 설치되어 있지만 충전횟수에는 포함하지 않는다.

입력

첫 줄에 노선 수 T가 주어진다. ( 1 ≤ T ≤ 50 )

각 노선별로 K, N, M이 주어지고, 다음줄에 M개의 정류장 번호가 주어진다. ( 1 ≤ K, N, M ≤ 100 )

출력

#과 노선번호, 빈칸에 이어 최소 충전횟수 또는 0을 출력한다.

코드

T = int(input())
for tc in range(1, T + 1):
    # k : 충전 후 한 번에 이동할 수 있는 정류장 수
    # n : 총 정류장 수
    # m : 충전소가 설치된 정류장 수
    # num_list : 충전소가 설치된 정류장의 위치
    k, n, m = map(int, input().split())
    num_list = list(map(int, input().split()))

    # location : 현재 있는 위치 charging : 충전 횟수
    location = 0
    charging = 0

    # 현재 위치 + 충전 후 이동할 수 있는 최대 정류장의 수가 총 정류장의 수보다 많아질 때까지 반복
    while location + k < n:
        # 최대 이동 가능한 거리 내에 충전소가 있는 지 확인하기 위한 반복문
        for i in range(k, 0, -1):
            # 현재 위치 + 최대 이동 거리 내에 충전소가 있는지 충전소 위치 리스트에서 확인
            if (location + i) in num_list:
                # 충전소가 있을 경우 떨어진 거리만큼 현재 위치에 더해줌
                location += i
                # 충전 횟수에 1을 더해줌
                charging += 1
                # 충전 후에는 for문을 종료
                break
        # 최대 이동 거리 내에 충전소가 없는 경우
        else:
            # 충전 횟수를 0으로 하고 while문 종료
            charging = 0
            break

    print('#{} {}'.format(tc, charging))

풀이 방법

우선 최대 이동 가능 거리 내에 충전소가 있는지 확인한 후 충전소가 있다면 그중 가장 먼거리의 충전소를 방문하도록 하고 해당 거리만큼 버스를 이동시킨다. 만약 이동 거리 내에 충전소가 없다면 break로 while문을 빠져나올 수 있게 해준다.
처음에는 어떻게 가장 먼 정류소를 선택할 수 있게 해줘야 할지 고민이 됐는데 for문의 인덱스를 최대 거리부터 0까지 -1씩 감소시키는 방법을 사용하여 문제를 해결했다.