전기버스2 Python(SW Expert Academy, SWEA)

난이도 : D3

문제번호 : 5208

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYGf7K180DFAVT#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

충전지를 교환하는 방식의 전기버스를 운행하려고 한다. 정류장에는 교체용 충전지가 있는 교환기가 있고, 충전지마다 최대로 운행할 수 있는 정류장 수가 정해져 있다. 충전지가 방전되기 전에 교체하며 운행해야 하는데 교체하는 시간을 줄이려면 최소한의 교체 횟수로 목적지에 도착해야 한다. 정류장과 충전지에 대한 정보가 주어질 때, 목적지에 도착하는데 필요한 최소한의 교환횟수를 출력하는 프로그램을 만드시오. 단, 출발지에서의 배터리 장착은 교환횟수에서 제외한다. 다음은 1번에서 출발 5번이 종점인 경우의 예이다. 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

---

2. 문제풀이

백트래킹 문제입니다. 여기서 중요한 부분은 최소한의 충전입니다. 그렇다면 충전횟수를 이용한 백트래킹이 가능하다고 생각합니다. 따라서 값을 무수히 큰 수를 저장한다음에 재귀를 돌면서 카운팅된 수가 저장된 수보다 커지면 재귀를 하지않도록 설정합니다. 위와 같이 가망이 없는 경우의 수를 처내면서 재귀를 돌게되면 문제가 풀립니다.

---

3. 소스코드

#D3 5208 전기버스2
def dfs(idx, _sum):
    global answer
    if answer < _sum: return
    if idx >= N:
        answer = _sum
        return
    count = station[idx]
    for i in range(count, 0, -1):
        dfs(idx+i, _sum+1)
 
 
for t in range(int(input())):
    answer = float('inf')
    station = list(map(int, input().split()))
    #0부터 시작하니까 -1
    N = station.pop(0) - 1
    #처음 충전은 안치니까 -1로 시작해서 보정해주기
    dfs(0, -1)
    print('#{} {}'.format(t+1, answer))