[SW Expert Academy] 5204. 병합 정렬

4466. 최대 성적표 만들기

---

문제)

 

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

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

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

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

 

 

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

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

 

 

[입력]

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

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

 

 

[출력]

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

 

 

 

 

풀이)

생각없이 백트래킹을 짰다가 시간초과에 두세번 부딪힌 문제이다.

 

처음에는 move를 설정해 가지치기를 실행했고, 더 시간을 줄일 방법을 생각해보다가

 

버스가 최대 거리만큼 움직인 다음 move를 먼저 설정하면 시간을 더 줄일 수 있겠다고 생각했다.

 

 

def recur(cur, cnt):
    global ans, move
    
    # 코드가 한번 돌고 move가 정의되면,
    # 그 이후부터는 cnt가 move를 초과시 가지치기
    if move < cnt:
        return
 
    if cur > li[0] - 1:
        ans = min(ans, cnt)
        move = cnt
        return
    
    # 멀리가는 것부터 실행
    for i in range(1, li[cur] + 1)[::-1]:
        recur(cur + i, cnt + 1)
 
 
T = int(input())
for _ in range(T):
    li = list(map(int, input().split()))
    # 무작정 큰 수
    ans, move = 1 << 20, 1 << 20
    recur(1, 0)
    print(f"#{_ + 1} {ans - 1}")

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.