5208. [파이썬 SW 문제해결 구현] 5일차 - 전기버스2

내가 지금까지 한 재귀 중 제일 자랑스러워서와 발상이 좋은 것 같아 올려봄.

또 오랜만에 타블렛 좀 써보고 싶었따.

처음에 index 0부터 시작해서 일단 숫자만큼 더하고 차차 빠지는 식으로 재귀. step을 +1씩 올리며 카운트 한다. best를 저장.

차차 +2까지 1씩해서 올리지 않고 바로 +2해서 -1만큼 한 이유는 코드의 편의성과 먼저 best를 설정해서 backtracking의 기준점 설정을 좀더 빠르게 하기 위함.

import sys

sys.stdin = open("sample_input.txt", "r")

def gobus(start_index,step, end_index):
    global scn
    # print("start_index" , start_index,"step",step,"end_index",end_index)
    if step > scn:
        return
    elif start_index >= end_index:
        # print("end.. step",step, "scn",scn)
        if step < scn:
            scn = step
            # print("scn",scn)
    else:
        for i in range(start_index+N[start_index],start_index,-1):
            gobus(i,step+1,end_index)


    return

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    N = list(map(int, input().split()))[1:]
    # print(N)

    scn = len(N)-1
    gobus(0,0,len(N))

    print("#{}".format(test_case),scn-1)

    # ///////////////////////////////////////////////////////////////////////////////////