Dynamic Programming - 11060

저번과 이어서 DP 문제를 연습하기 위해 가져왔다.

이번에는 AI의 도움 없이 혼자 풀이하였다.

문제 설명

1. 미로의 크기인 1차원 배열의 크기 N과 미로의 정보인 Ai가 주어진다.
2. 미로의 정보에는 이동할 수 있는 칸의 수가 쓰여져있다.
3. N번째 칸으로 갈 때 최소 점프 수를 구하여라.

문제 풀이

문제를 보자마자 저번 포스트에서 다룬 11053 문제의 접근법이 떠올랐다.

같은 DP문제로 점화식을 통해 작은 문제서부터 큰 문제를 해결해나가는 방식을 똑같이 사용해보겠다.

1. for i < N(N번째 칸까지 최소 이동값을 구하기 위해 반복)
2. for j < i(i가 최종 목적지일 경우 그 전에 있는 칸을 모두 탐색하기 위해 반복)
3. if (i-j)(두 칸 사이의 거리) <= A[j](이동 가능 칸수)(두 칸 사이의 거리보다 이동 가능한 칸 수가 작은 경우)
4. result[i] = Min(result[i], result[j] + 1)(i가 최종 목적지일 경우 최소 이동 거리)

여기서 Min으로 작은 값을 찾기 위해서는 result를 0으로 초기화 하면 안되고 예상 결과 범위 외의 값으로 설정해야 한다.

입력 조건이 "첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다."이기 때문에,

미로의 최대 크기는 1000이고 최대로 나올 수 있는 값은 못가는 경우를 제외한 1칸씩 이동하는 방식이다.

따라서 최대 출력값은 1000이다.

 

따라서 최소 이동 횟수를 담는 배열은 1001로 초기화하여 비교하였다.

코드 풀이

using System;
using System.Collections.Generic;
using System.Linq;

namespace StudyCS
{
    class Program
    {
        public static void Main(string[] args)
        {
            //1*N 사이즈 맵
            //칸마다 정수 하나
            //쓰여있는 정수이하의 수 만큼 이동 가능
            //최소 이동 수를 구하기

            //그렇다면 점화식은 i번째 칸에 도달하는 방법 중 최소 값일듯?
            //이전칸 모두 탐색
            //for i < N
            //for j < i
            //if (i-j)(두 칸 사이의 거리) <= A[j](이동 가능 칸수)
            //result[i] = Math.Min(result[i], result[j] + 1)(최소 값 찾기)
            int N = int.Parse(Console.ReadLine()); //미로의 크기
            int[] A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse); //미로의 정보

            //최소 이동 횟수를 담는 배열, 입력조건이 1000이하기 때문에 1칸씩 움직이는걸로 최대 1000임
            int[] result = Enumerable.Repeat(1001, N).ToArray();
            result[0] = 0;
            for (int i = 1; i < N; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if((i-j) <= A[j])
                    {
                        result[i] = Math.Min(result[i], result[j] + 1);
                    }
                }
            }
            if (result[N-1] > 1000)
            {
                Console.WriteLine(-1);
                return;
            }
            Console.WriteLine(result[N-1]);
        }
    }
}

위에서 설명한 것과 같다.

1001로 초기화 하고 최소 값을 찾는다.

하지만 마지막 i번째(index로 찾아야하기 때문에 -1) 값이 1000보다 크다면 초기 값인 1001이 담긴 것이기 때문에 이동하지 못한 것이다.

따라서 -1을 출력한다.

그리고 1000보다 작다면 이동이 가능한 것이기 때문에 값을 그대로 출력한다.