[2일차][재귀함수] 전기버스

- 문제 설명

충전지를 교환하는 방식의 전기 버스

교체하면 해당 거리만큼 갈 수 있음

최소 교체로 목적지까지 도달하기

정류장	1	2	3	4	5
충전지	2	3	1	1

위와 같을때는 

출발지점에서 2칸 갈 수 있고, 2번에서 교체해서 5번까지 한번에 갈 수 있으므로 1번

- 입력

1 // 테스트케이스

5 2 3 1 1 // 첫번째 수는 정류장 갯수 나머지는 정류장마다 충전지 용량

- 출력

#1 1 // 테스트케이스 최소 충전 수 

- 입력 예시

3
5 2 3 1 1
10 2 1 3 2 2 5 4 2 1
10 1 1 2 1 2 2 1 2 1

- 출력 예시

#1 1
#2 2
#3 5

- 코드

#include "stdio.h"

int input[100];

int charge[100];

int chargeCount = 0;

int stopNum;

void canReachDesination(int current, int distance);

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        

        scanf("%d",&stopNum);

        for(int i = 0; i< stopNum; i++) // 충전소 초기화

        {

            charge[i] = 0;

        }

        for(int i=0;i<stopNum-1;i++) // 충전소 위치에 충전량 표시

        {

            scanf("%d",&input[i]);

            charge[i] = input[i];

        }

        chargeCount = 0; // 카운트 초기화

        canReachDesination(0, charge[0]);

        printf("#%d %d\n",tc,chargeCount);

    }

    return 0;

}

void canReachDesination(int current, int distance)

{

    if(current+distance >= stopNum -1) // 지금 위치에서 충전량을 더했을때 목적지보다 길면 도착 성공

        return ;

    int maxDistance =0;

    int maxIndex = current;

    for(int i= current+1; i<=current+distance;i++) // 갈 수 있는 거리 상에서 가장 큰 충전량 찾기

    {

        if(charge[i] > maxDistance) // 가장 큰 충전량

        {

            maxIndex = i;

            maxDistance = charge[i];

        }

        else if(charge[i] == maxDistance) // 충전량이 같은경우 index만 옮김

        {

            maxIndex = i;

        }

    }

    if(maxDistance == 0) // 충전량이 다 떨어져서 더이상 갈 수 없는 경우 실패처리

        return;

    else // 아직 갈 수 있는 경우 충전횟수를 늘리고 충전소에서 다시 시작

    {

        chargeCount++;

        canReachDesination(maxIndex, maxDistance);

    }

}