SWEA 5208 전기버스2 (파이썬)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

---

아이디어

• 전기 배터리를 가스라고 부르겠음
• 가스가 있는 경우와 없는 경우로 나누어서 재귀함수를 만든다.
• 함수에 넘겨줄 매개변수는 index==정류장번호, cnt==가스 넣는 개수, gas==gas양

 

---

풀이 및 해설(주석)

def solve(index, cnt, gas):
    global rst
    gas -= 1
    if index >= (N-1):
        rst = min(rst, cnt)
        return
    if cnt >= rst: return

    #가스가 있는 경우
    if gas:
        solve(index+1, cnt, gas)
    # 가스가 없는 경우
    solve(index+1, cnt+1, info[index])




for tc in range(int(input())):
    N, *info = map(int, input().split())

    rst = 1e9
    
    # 이미 출발해서 0은 포함 안함
    solve(1, 0, info[0])

    print(f'#{tc+1}', rst)