[SWEA][D3][#04831] 전기 버스

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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을 출력한다.

예제

입력

3
3 10 5
1 3 5 7 9
3 10 5
1 3 7 8 9
5 20 5
4 7 9 14 17

출력

#1 3
#2 0
#3 4

My Sol

T = int(input())
for tc in range(1, T+1):
    # K: 최대이동가능 정류장 / N: 종점 / M: 충전기 개수
    K, N, M = map(int, input().split())
    arr2 = list(map(int, input().split()))  # 충전기 정류소
    arr = [0] * (N + 1)

    for n in arr2:
        arr[n] += 1

    for i in range(N):
        arr[i + 1] += arr[i]

    cnt = 0  # 충전횟수
    p = 0    # 현재 위치

    while (p+K) < N:
        cnt += 1
        if arr[p] == arr[p+K]:
            cnt = 0
            break

        p += K

        while arr[p] == arr[p-1]:
            p -= 1

    print(f'#{tc} {cnt}')

입력되는 값들을 모두 처리하여 변수에 할당한다. 충전소가 있는 정류소를 1, 없는 구간은 0으로 하는 배열 arr2를 만들었다. 이를 카운팅 정렬의 누적값 카운트 배열의 방식을 사용하여 처리했는데, 현재값과 이후 값을 더한 값을 이후 값으로 재정의하는 누적 카운팅 배열 arr을 만드는 것이다.

이후 현재의 위치를 의미하는 p 변수를 0으로 설정하고, 최대 이동 거리인 K를 계속 더하면 처리하는 반복에 진입한다. 반복을 돌다가, 현재 위치(p) + 최대 이동 가능 거리(K)를 더한 값이 종점인 N보다 같거나 거친다면 반복을 멈추도록 한다.

우선 현재 위치에서 K를 더했다는 것은 충전을 한 번 했다는 얘기이므로 충전 횟수 cnt에 1을 더해준다. 그런데 만약 현재 위치 p와 현재 위치에 K를 더한 값이 같다면 그 사이에 충전소가 없었다는 이야기이므로 cnt를 0으로 바꾸고 반복을 탈출하여 cnt를 출력하면 된다.

그것이 아니라면 그 사이에 충전소가 있다는 의미이므로, 최대이동 가능한 거리까지 간 뒤에 값이 달라지는 지점까지 뒤로 되돌아가는 것이다. 값이 달라진다는 것은 해당 위치에 충전소가 있다는 말이므로, 해당 위치에 멈추도록 p를 설정한다. 이후 다시 반복을 시작하면 되는 것이다.