dp로 뒤에서부터 최솟값을 가져와 0까지 역산했습니다. for test in range(1, int(input()) + 1): N, *battery = map(int, input().split()) dp = [float('inf')] * N dp[N - 1] = 0 for i in range(N - 1, -1, -1): for j in range(i - 1, -1, -1): if j + battery[j] >= i: dp[j] = min(dp[j], dp[i] + 1) print(f'#{test} {dp[0] - 1}')