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

출처

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

• 시간 : 10개 테스트케이스를 합쳐서 C/C++의 경우 1초 / Java의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


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

 

Pass 코드

T = int(input())
t = 1

while T-t >= 0:
    K, N, M = map(int, input().split())
    bus = [0 for _ in range(N+1)]
    m = list(map(int, input().split()))
    for i in m:
        bus[i] = 1

    now = 0 
    nowK = 0 + K
    cnt = 0

    while nowK < N:
        if now == nowK:
            cnt = 0
            break
        if bus[nowK] == 1:
            now = nowK
            nowK = now + K
            cnt += 1
        elif bus[nowK] == 0:
            nowK -= 1

    print("#"+str(t), cnt)
    t += 1

 

설명 첨부

T = int(input())
t = 1

while T-t >= 0:
    # K : 충전하면 갈 수 있는 정거장 수
    # N : 종점
    # M : 충전기가 위치한 정거장 수
    K, N, M = map(int, input().split())
    # bus : 노선 // 0:충전기X정거장 1:충전기O정거장
    # bus = [0 0 0 0 0 0 0 0 0 0 0] 초기화
    bus = [0 for _ in range(N+1)]
    # m : 충전기가 위치한 정거장 노드 [1 3 5 7 9]
    m = list(map(int, input().split()))
    # 충전기가 있는 정거장은 1로 // bus = [0 1 0 1 0 1 0 1 0 1 0]
    for i in m:
        bus[i] = 1
    
    # 3번째 정거장에서 충전, 6번째에는 충전기가 없으니까 5번째에서 충전, 8번째 없으니까 7번째에서 충전 >> 10번째 도달 (종료)
    # 1. 현재 정거장에서 (현재 + K)번째 정거장까지 갈 수 있음
    # 2. (현재 + K)번째 정거장에 충전기가 없으면 노드를 하나씩 줄여가며 충전기가 있는 정거장을 찾아 충전
    # 3. 충전하면, 현재 버스 위치를 충전한 정류장 인덱스로 갱신 & 충전횟수 1 증가
    # 4. (현재 + K)번째 정거장이 종점 이상이면 종료

    # now : 현재 위치
    now = 0 
    nowK = 0 + K
    cnt = 0

    while nowK < N:
        # 현재위치부터 (현재+K)번째 사이에 충전기가 있는 정거장이 없으면 0
        if now == nowK:
            cnt = 0
            break
        # nowK 번째 정거장에 충전기가 있는 경우
        if bus[nowK] == 1:
            now = nowK
            nowK = now + K
            cnt += 1
        #nowK 번째 정거장에 충전기가 없는 경우
        elif bus[nowK] == 0:
            nowK -= 1

    print("#"+str(t), cnt)
    t += 1