SWEA 4831 전기버스 (python)

4831. [파이썬 S/W 문제해결 기본] 1일차 - 전기버스 D3

 

 

연관문제

2021.04.21 - [Algorithm] - SWEA 5208 전기버스2 (python)

 

문제

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

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

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

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

[예시]

다음은 K = 3, N = 10, M = 5, 충전기가 설치된 정류장이 1, 3, 5, 7, 9인 경우의 예이다.

[입력]

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

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

[출력]

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

풀이

T = int(input())

def bus(info_numbers,charger):
    # 각각의 정보에 접근
    K = info_numbers[0]
    N = info_numbers[1]
    M = info_numbers[2]

    # 충전기 수 자체가 부족할 경우
    if N//K >M:
        return 0

    # 충전기 정보를 표현해주기 위한 초기값
    counter = [0]*N
    # 충전기 정보를 받아와 1로 표시
    for number in charger:
        counter[number] = 1



    # 현재위치 now
    now = 0
    # 목적지 goal
    goal = N
    # 충전 횟수 count
    count = 0

    # now가 goal보다 작다면 => goal에 도작하지 않았다면
    while now < goal:
        # 다음위치 now == 현재위치 + 최대갈수 있는거리
        after = now + K
        # 다음위치가 goal에 도착하거나 넘는다면 멈추기
        if after >= goal:
            break

        # now~after 사이의 정류소 리스트 between
        between = counter[now:after + 1]
        charge = 0

        # between을 돌면서 인덱스와 값(충전소가 있다면 1) 가져오기
        for idx, i in enumerate(between):
            # 충전기가 있다면 1, 따라서 if문 통과 => between중에서 제일 마지막 충전기 위치 찾기
            if i:
                charge = idx

        # 충전기 없으면 이동 불가
        if charge == 0:
            count = 0
            break

        now += charge
        count += 1
    return count



for tc in range(1, T+1):
    # K,N,M 정보가 담긴 리스트
    info_numbers = list(map(int,input().split()))

    #충전기 정보
    charger = list(map(int, input().split()))

    # 결과
    result = bus(info_numbers, charger)
    print("#{} {}".format(tc, result))