🎈문제

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

---

📍풀이

• N이 최대 100까지 가는 것을 보면서 그리드나 백트래킹으로 문제를 풀어야 된다고 생각 해야 한다.
• 배터리를 교체하는 것은 교체O / 교체X 라는 두가지 선택지가 있으므로 이진트리 형식으로 생각할 수 있다.
• 백트래킹으로 풀어보자

---

📍조건

• 1<=T<=50
• 3<=N<=100, 0 ＜ Mi ＜ N

---

📍풀이순서

• 입력하는 값이 lst에 한줄에 주어진다는 점을 고려해 N을 작성
• DFS를 구현하는 과정에서 필요한 것은 (lst의 인덱스 n, 배터리를 교환하는 횟수 cnt, 배터리의 잔량 sm)
• 가지치기 / 기저 조건(함수를 종료하는 조건) / 메인로직을 작성한다.
• 메인 로직에서 배터리 교체O / 교체x 하는 경우에 따른 재귀를 진행한다.
  ⭐유망한 답이 먼저 나오는 방향으로 재귀를 진행하며 시간을 절약

---

💻코드1 (실행시간 705ms)

def dfs(n, cnt, sm):
    global ans
    # 가지치기
    if ans <= cnt:
        return

    # 기저 조건
    if n == N:
        ans = min(ans, cnt)
        return

    # 메인 로직 
    dfs(n+1, cnt+1, lst[n]-1) # 충전기 교환을 할 때
    if sm > 0:
        dfs(n+1, cnt, sm-1) # 충전기 교환을 하지 않을 때
    

T = int(input())
for tc in range(1, T+1):
    lst = list(map(int, input().split()))
    N = lst[0]

    # 최대로 충전기를 교환하는 횟수
    ans = N
    dfs(2, 0, lst[1]-1)

    # 출력
    print(f'#{tc} {ans}')

💻코드2 (실행시간 337ms)

def dfs(n, cnt, sm):
    global ans
    # 가지치기
    if ans <= cnt:
        return

    # 기저 조건
    if n == N:
        ans = min(ans, cnt)
        return

    # 메인 로직 
    # 유망한 답이 먼저 나오는 방향으로 호출을 진행하면 가지치기를 시간을 아낄 수 있다.
    if sm > 0:
        dfs(n+1, cnt, sm-1) # 충전기 교환을 하지 않을 때
    dfs(n+1, cnt+1, lst[n]-1) # 충전기 교환을 할 때
    
    

T = int(input())
for tc in range(1, T+1):
    lst = list(map(int, input().split()))
    N = lst[0]

    # 최대로 충전기를 교환하는 횟수
    ans = N
    dfs(2, 0, lst[1]-1)

    # 출력
    print(f'#{tc} {ans}')

---

⭐코드에 따른 시간 차이

• 코드1 (실행시간 705ms)
• 코드2 (실행시간 337ms)

그 이유는? (틀린 그림 찾기)