[ SW Expert Academy ] 5208 전기버스2

음 .. 언제쯤 재귀를 자유자재로 사용할까.. 꽤 속상하네?

 

제출도 못 하고 돌아가지 않는 내 문제 풀이..

def get_min_exchange(n, bus_stops, now, cnt):
    global min_cnt
    if min_cnt <= cnt:
        return
    if now >= n:
        # 카운트 최솟값인지 체크해서 갱신
        min_cnt = min(min_cnt, cnt)
        return
    for i in range(now+1, now + bus_stops[now]):
        get_min_exchange(n, bus_stops, i, cnt + 1)


import sys
sys.stdin = open("sample.txt", "r")


if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T + 1):
        answer = 0
        data = list(map(int, input().split()))
        n = data[0]
        bus_stops = data[1:]
        min_cnt = 1e9
        get_min_exchange(n, bus_stops, 0, 0)

        print("#" + str(test_case), 0)

 

 

 

1 차 제출 . [ 10 / 10 ] PASS

수정해서 다시 제출했다.

 

def dfs(idx, curr_sum, n, station):
    global answer
    if answer < curr_sum:
        return
    if idx >= n:
        answer = curr_sum
        return
    count = stationc[idx]
    for i in range(count, 0, -1):
        dfs(idx+i, curr_sum+1)
if __name__ == "__main__":
    T = int(input())
    for test_case in range(1, T+1):
        answer = 1e9
        station = list(map(int, input().split()))
        n = station.pop(0)-1
        dfs(0, -1, n, station)
        print("#{} {}".format(test_case, answer))