[SWEA 14160번] 전기버스2 - 파이썬(python)

SW Expert Academy

문제

충전지를 교환하는 방식의 전기버스를 운행하려고 한다. 정류장에는 교체용 충전지가 있는 교환기가 있고, 충전지마다 최대로 운행할 수 있는 정류장 수가 정해져 있다.

충전지가 방전되기 전에 교체하며 운행해야 하는데 교체하는 시간을 줄이려면 최소한의 교체 횟수로 목적지에 도착해야 한다.

정류장과 충전지에 대한 정보가 주어질 때, 목적지에 도착하는데 필요한 최소한의 교환횟수를 출력하는 프로그램을 만드시오. 단, 출발지에서의 배터리 장착은 교환횟수에서 제외한다.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 한 줄에 정류장 수 N, N-1개의 정류장 별 배터리 용량 Mi가 주어진다. 3<=N<=100, 0 ＜ Mi ＜ N

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이

• 버스의 최소 배터리 교체 횟수를 출력해야한다.
• 첫번째 정류장에서는 횟수를 세지 않으므로 기본 시작값을 2번째 정류장인 상태에서 시작한다.
• 정류장을 하나 지날때마다 정류장 번호(idx)는 +1 되고 배터리 상태는 -1 된다.
• 또한 배터리는 교체되는 것이므로 더하는 것이 아니라 변경된 배터리값으로 바꾸어주어야 한다.
• 시간을 줄이기 위해 최소값을 넘는 카운트에서 리턴하고 현재 값이 0보다 클때는 교체하지 않는 방향으로 계산한다.

코드

def dfs(cnt, idx, now):
    global mn
    if mn <= cnt:
        return
    if idx == N:
        mn = min(cnt, mn)
        return
    if now > 0:
        dfs(cnt, idx + 1, now - 1)
    dfs(cnt + 1, idx + 1, bus_stop[idx] - 1)

T = int(input())
for test_case in range(1, T + 1):
    bus_stop = list(map(int, input().split()))
    N = bus_stop[0]
    mn = 21e8
    # cnt. 시작 인덱스. 현재 배터리
    dfs(0, 2, bus_stop[1] - 1)

    print(f'#{test_case} {mn}')