[DP] 11060번 - 점프 점프 (14일차)

//scanf 에러 방지를 위한 define
#define _CRT_SECURE_NO_WARNINGS
//입력받은 두 수 중 작은 값을 반환하는 MIN 함수 선언 
#define MIN(a,b) (a<b ? a:b)
#include <stdio.h>
//calloc을 사용하기 위한 모듈 include
#include <stdlib.h>

//메인 함수 선언
int main()
{
    //미로의 개수 n입력 
    int n;
    scanf("%d", &n);
    //동적 할당으로 n만큼의 크기를 가지는 미로, dp 배열 생성 (0으로 초기화 필요x)
    int * maze = (int *)malloc(sizeof(int) *n);
    int * dp = (int *)malloc(sizeof(int) *n);
    //maze 배열에 각각의 미로의 크기를 입력받음과 동시에 dp 배열 -1로 초기화
    for(int i=0; i<n; i++) 
    {
        scanf("%d", &maze[i]);
        //탐색이 이루어지지 않은 지점 or 도달할 방법이 없는 지점을 표시하는 -1
        dp[i] = -1;
    }
    //1번째 미로는 도달하는 데 이동이 필요하지 않기에 0회으로 설정
    dp[0] = 0;
    //모든 미로 칸에 대해 i를 이용해 순차 탐색하기
    for(int i=0; i<n; i++)
    {
        //해당 미로 칸의 숫자만큼 j를 이용해 앞으로 순차 탐색
        for(int j=1; j<maze[i]+1; j++)
        {
            //맨 끝 미로칸까지 도달해 더 앞으로 탐색할 수 없는 경우
            if(i+j > n)
            {
                //해당 미로 칸에 대한 탐색 종료
                break;
            }
            //해당 미로 칸이 도달한 방법이 없는 칸이 아니고
            //앞으로 탐색하고 있는 칸이 탐색된 것이 없을 때
            else if(dp[i] != -1 && dp[i+j] == -1)
            {
                //앞으로 탐색하고 있는 칸에
                //해당 칸에 저장된 도달하기 위해 필요한 점프 횟수에 1을 더함
                //해당 칸을 밟고 탐색하고 있는 칸으로 이동할 수 있다는 의미
                dp[i+j] = dp[i] + 1;
            }
            //해당 미로 칸이 도달할 방법이 없는 칸이 아니고
            //앞으로 탐색하고 있는 칸이 탐색된 적이 있을 때
            else if(dp[i] != -1 && dp[i+j] != -1)
            {
                //앞으로 탐색하고 있는 칸에
                //이미 저장된 이동 횟수와 해당 칸에 저장된 이동횟수 +1 중
                //작은 값을 저장한다 (적은 이동횟수일수록 좋기 때문)
                dp[i+j] = MIN(dp[i+j], dp[i]+1);
            }
        }
    }
    //마지막 미로 칸까지 탐색이 끝났을때 dp의 마지막 인덱스에 저장된 이동횟수를 출력
    printf("%d", dp[n-1]);
}