-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbacktracking.py
More file actions
35 lines (27 loc) · 847 Bytes
/
backtracking.py
File metadata and controls
35 lines (27 loc) · 847 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys
def main():
stdin = sys.stdin
T = int(input())
for test_case in range(T):
N, *M = map(int, input().split())
# 초기값
bus = 0
bus_battery = M[bus]
cnt = 0
while bus + bus_battery < N-1:
max_charge = 0
next_bus = None
for i in range(bus_battery, 0, -1):
charge = M[bus+i] - (bus_battery - i) # 충전가능한 양
if charge > max_charge: # 최대값을 찾아
max_charge = charge
next_bus = bus+i
if next_bus is None:
cnt = -1
else:
bus = next_bus
bus_battery = M[bus]
cnt += 1
print('#{} {}'.format(test_case, cnt))
if __name__ == 'main':
main()