SWEA 5208 전기버스2 (python)

5208. [파이썬 S/W 문제해결 구현] 5일차 - 전기버스2

 

[파이썬 S/W 문제해결 구현] 5일차

2021.04.21 - [Algorithm] - SWEA 5208 전기버스2 (python)

2021.04.21 - [Algorithm] - SWEA 5209 최소 생산 비용 (python)

 

연관문제

2021.04.19 - [Algorithm] - SWEA 4831 전기버스 (python)

SWEA 4831 전기버스 (python)

문제

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

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

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

다음은 1번에서 출발 5번이 종점인 경우의 예이다.

정류장	1	2	3	4	5
충전지	2	3	1	1

1번에서 장착한 충전지 용량이 2이므로, 3번 정류장까지 운행할 수 있다. 그러나 2번에서 미리 교체하면 종점까지 갈 수 있다.

마지막 정류장에는 배터리가 없다.

[입력]

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

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

[출력]

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

코드

import sys
sys.stdin = open("sample_input.txt")

T = int(input())

# 버스가 가면서 배터리 충전하는 함수
# idx는 정류장의 위치, cnt는 충전횟수
def bus(idx, cnt):
    global result
    # 시간초과를 피하기 위해서 더 작은 값이 안나오면 중지
    if cnt >= result:
        return
    # 만약 목적지를 넘는다면
    if idx >= N -1:
        # 지금 센 횟수랑 결과값이랑 비교해서 작다면 갱신
        if cnt <= result:
            result = cnt
        return
    # 한번 충전해서 갈수 있는 곳을 다 둘러보는 반복문
    # 해당 정류장에서 해당하는 배터리로 갈수 있는 경우의 수를 모두 둘러본다.
    for i in range(info[idx]):
        # 그 경우의 수에 해당하는곳으로 옮겨서 다시 살펴보자
        # i가 0부터 시작하니까 1씩 더 더한다.
        bus(idx+i+1, cnt +1)

for tc in range(1, T+1):
    info = list(map(int, input().split()))
    N = info.pop(0)
    result = 10000
    # 최초 들어갈때 충전을 한다고 가정하므로 cnt에 -1을 넣어준다.
    bus(0, -1)

    print("#{} {}".format(tc, result))

추가

# 시간초과를 피하기 위해서 더 작은 값이 안나오면 중지
    if cnt > result:
        return

크다고만 뒀다가 바로 시간초과가 발생하였다.

• 풀수 있는 다른 방법이 있지 않을까?🙄