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

SW Expert Academy에서 학습용으로 문제를 가져왔습니다. 문제가 될 시 수정, 삭제하겠습니다.

https://swexpertacademy.com/main/main.do

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

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

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

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

예시

[입력]

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

[출력]

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

input

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

output

#1 3
#2 0
#3 4

code

T=int(input())

for test_case in range(1,T+1):
    #K: 최대 이동 가능 수
    #N: 종점
    #M: 충전기 정류장 수
    K, N, M =map(int,input().split())

    #charge:충전기 위치
    charge=list(map(int,input().split()))+[N+K,N+K] #N+K리스트를 2개 추가해주는 이유는 밑에 while문에서 마지막 값이 범위를 벗어나기 때문에 만들어준것이다.
    
    #현재 위치
    here=0

    #정류장 위치
    i=0

    #충전 할때마다 +1
    cnt=0

    while here +K<N: #현재위치에서 최대 이동가능한 만큼 이동했을때 종점보다 작을때 동안!
        if here+K>=charge[i+2]: #만약에 현재위치에서 최대 이동가능한 만큼 이동한 게 충전소 위치의+2보다 크다면
            here = charge[i+2] #현재 위치가 그 충전소 위치가 되고
            cnt+=1             #충전을 한번 해주고
            i+=3               #정류장 위치를 3만큼 더해준다.
            continue

        elif here+K >= charge[i+1]: #또한 만약에 현재위치에서 최대 이동가능한 만큼 이동한 것이 충전소 위치+1보다 크거나 같으면
            here = charge[i+1]      #현재 위치가 그 충전소 위치가 되고
            cnt+=1                  #충전을 한번 해주고
            i+=2                    #정류장 위치를 2만큼 더해준다.
            continue

        elif here+K < charge[i]:     #또한 만약에 현재위치에서 최대 이동가능한 만큼 이동한 것이 충전소 위치보다 작으면
            cnt=0                    #충전을 할 수 없으므로 cnt를 0으로 해준다. 
            break                    #그리고 더 이상 움직일 수 없다.

        else: 
            here = charge[i]           #나머지 경우는 현재위치와 충전소 위치를 같게 해주고
            cnt +=1                    #충전을 한번 해주고
            i+=1                       #정류장 위치를 한번 더해준다.


    print("#%d %d"%(test_case,cnt))