[swea] 5208. 전기버스2 / python 파이썬

문제

 

thinking

정류장별 배터리 용량을 리스트로 만든 후, 1번 정류장부터 돌면서 교환횟수를 구해 비교했다.

최소한의 교체횟수를 묻고 있으므로 이전횟차까지의 결과값보다 같거나 크면 return 시키도록 함수를 구성했다.

함수의 인자로 현재위치(i), 최대로 갈 수 있는 범위(max_i), 해당타임 교환횟수(cnt)를 두어 일단 갈 수 있는 만큼 최대로 가보면서 cnt 값을 비교했다.

+ 교환횟수처럼 계속 변하는 값을 함수의 인자로 두면 코드짜는게 더 쉽다. 굿 ! ! !

 

코드

def dfs(i, max_i, cnt):  # 현재위치(인덱스), 최대로 갈 수 있는 범위, 해당타임 교환횟수
    global res
    if cnt >= res:
        return
    if max_i >= N:
        res = min(cnt, res)
        return
    for j in range(max_i, i, -1):
        dfs(j, j + M[j], cnt + 1)


T = int(input())
for tc in range(1, T+1):
    tmp = list(map(int, input().split()))
    N = tmp[0]
    M = [0] + tmp[1:]  # 정류장 별 배터리 용량(1~N-1)

    res = 10000
    dfs(1, 1+M[1], 0)
    print("#{} {}".format(tc, res))