SWEA 전기버스 풀이2: 재귀 활용해서 풀기

https://gkim1011.tistory.com/10

SWEA 13565 전기버스

 

요즘 재귀문제를 많이 풀어서 그런지

bucket으로 말고 재귀로도 이 문제를 풀 수 있겠다는 생각을 했다.

지금 있는 칸을 매개변수 now로 받아오고, 재귀로 들어가면서 now를 계속 바꿔주는 코드이다.

 

T = int(input())

for tc in range(1, T+1):
    K, N, M = map(int, input().split())
    arr = list(map(int, input().split()))

    bucket = [0]*(N+1)

    for i in range(M):
        bucket[arr[i]] =1

    cnt = 0 #몇번만에 도달했는지

    def rcr(now):
        global cnt

        if now>=N-K:
            return

        flg = 0
        for i in range(K, 0, -1):
            if bucket[now+i]==1:
                cnt+=1
                flg = 1
                rcr(now+i)
                break
        if flg == 0:
            cnt = 0
            return



    rcr(0)
    print(f'#{tc} {cnt}')