[맛있는물회] <SWEA알고리즘> 4831번 "전기 버스 "

문제 조건

---

---

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

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

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

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

 

Input

---

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

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

 

Output

---

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

 

 

생각한 아이디어

---

생각보다 시간이 꽤 걸렸다,,,,

먼저 정류장을 갯수만큼 List를 만든다음에 0으로 초기화를 했다. 그리고 충전기가 설치된 정류장의 input 값을 토대로 List를 Index에 맞춰서 Count해주었다. 

그다음 Original Position 과 가상의 Position을 만들었다.

버스가 한번에 갈 수 있는 거리를 기준으로 가상의 Position은 움직인다. 만약 그곳에 충전기가 없다면 뒤로 하나씩 움직인다. 

그러다 가상의 위치와 현재위치가 만난다는 것은 충전을 못한다는 의미이다. 따라서 그렇게 되면 0을 출력하고 끝이난다. 

그게 아니라면 계속해서 앞으로 움직이며 충전하는 횟수를 Count한다. 

움직일 수 있는 최대의 거리를 먼저 움직이는 이유는 충전하는 최솟값을 구하기 때문이다.

 

소스코드

T = int(input())
for TC in range(1, T+1):
    k,n,m = map(int,input().split())
    arr = list(map(int, input().split()))
    stop = []
    for i in range(200):
        stop.append(0)
    for i in range(m):
        stop[arr[i]] = 1
    
    j=0
    pos_org = 0
    pos2 = k
    cnt = 0
    while 1:
        if pos2 >= n:
            print("#%d %d" %(TC, cnt))
            break

        if stop[pos2] == 1:
            cnt+=1  #Find the Gas station
            pos_org = pos2
            pos2 += k
        else:
            pos2 -= 1 #backstep
            if pos2 == pos_org:#We can not arrive
                print("#%d %d" %(TC, 0))
                break    

 

*파이썬 문법 정리