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

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

🚩 문제설명

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

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

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

다음은 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는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

---

입력

3
5 2 3 1 1
10 2 1 3 2 2 5 4 2 1
10 1 1 2 1 2 2 1 2 1

출력

#1 1
#2 2
#3 5

---

📝 문제풀이

---

def dfs(idx):
    global charge, result

    if idx >= len(lst):
        if result >= charge:
            result = charge
        return

    if result <= charge:
        return

    for i in range(idx+lst[idx], idx, -1):
        charge += 1
        dfs(i)
        charge -= 1


T = int(input())

for test_case in range(1, T + 1):
    lst = list(map(int, input().split()))
    N = lst[0]
    result = 987654321
    charge = 0
    dfs(1)

    print(f'#{test_case} {result-1}')

---

🔧 해결방안

1. 정류장 idx를 체크하여 종점에 이르기 전까지 충전 횟수를 세준다.
   종점에 이르면 지금까지 충전 횟수 charge가 최종 최소 값인 result보다 작거나 같은지 확인한다.
   
   
2. 새로운 정류장에 도달하고자 할때마다 dfs를 사용하여 재귀호출한다.
   
   
3. 재귀호출 과정 중, 유망하지 않으면, 지금 충전하고 있는 횟수가 이전에 충전이 완료된 횟수를 넘어가면 굳이 더 따질 필요가 없기 때문에 재귀호출을 return하여 백트래킹한다.
   if result <= charge: return
   
   
4. 전기를 충전 하기 위해서는, 예를 들면 1번 정류장이 2칸 움직일 수 있게 충전한다면 2, 3번 정류장을 갈 수 있다는 뜻이므로 두개의 정류장을 따져줄 수 있게 반복문(for문)을 돌려 재귀호출 한다.