문제 설명

정의

전기버스가 있다. 전기버스는 한번 충전 후 K칸 만큼 갈 수 있다. 총 가야할 거리는 N이고, 충전소의 개수는 M개이다. 충전소의 위치가 주어지고, 전기버스는 최소한의 충전을 하며 N까지의 거리를 이동할 때, 총 몇개의 충전소를 들렸는지 구하여라

제한

충전이 불가능해 N까지 가지 못할 경우 0을 반환한다.

입력

첫 줄에 테스트케이스의 개수가 주어지며 그 다음 줄에 한번 충전 후 갈 수 있는 칸 수 K, 총 가야할 거리 N, 충전소 개수 M을 입력받는다. 그 다음 줄에 충전소의 위치를 입력받는다.

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

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 각각의 테스트 케이스에서 목적지에 도달할 수 있을 경우 충전소를 들린 횟수를 출력하고, 도달하지 못할 경우 0을 출력한다.

#1 3
#2 0
#3 4

문제 풀이

1. N까지 도달할 때까지 반복한다.
2. 한번 충전 후 갈 수 있는 최대한의 위치 i + K를 탐색하고, 충전소가 없을 경우, 한칸 씩 줄인다.
3. 있다면 그곳을 i로 최신화하고 2번 과정을 반복한다.
4. 목적지에 도달했다면 이동한 횟수를 출력하고, i 와 i + K 사이에 충전소가 존재하지 않을 경우 반복을 중단하고 0을 출력한다.

코드

for tc in range(1, T+1):
    K, N, M = map(int, input().split())
    input_arr = list(map(int, input().split()))
    arr = [0] * N
    for m in range(M):
        arr[input_arr[m]] = 1

    i = 0
    result = 0

    while i < N:
        for j in range(K):
            # 목적지에 이미 들어왔으면 반복문 종료
            if i+K-j >= N:
                i = N
                break
            # K만큼 떨어진 곳부터 하나씩 줄여가며 충전소 탐색
            if arr[i+K-j] == 1:
                i = i+K-j
                result += 1
                break
            # 없으면 result = 0 하고 반복문 종료
            if j == K-1:
                result = 0
                i = N
                break

    print(f"#{tc} {result}")