[ 백준 11060 ] 점프점프(2) (C++)

백준의 점프점프(11060) 문제이다.

[ 문제 바로가기 ]

기존에 이 문제에 대한 풀이글을 포스팅 한 적이 있었지만, 그 글에서는 풀이방법을

1. BFS를 사용한 방법

2. DFS + DP를 사용한 방법

이 2가지 방법을 이용해서 풀이하였다.

[ 기존의 점프점프(11060) 풀이 보러가기 ]

이번 글에서는 DP만을 사용한 방식을 이용해서 풀이하는 방법에 대해서 알아보자.

[ 문제풀이 ]

간단한 예시를 이용해서 문제에 접근해보자.

[ 1 2 1 1 2 ] 라는 예시를 가지고 문제를 한번 해결해보자.

지금부터는 수식 하나를 사용해서 풀이를 진행할 것이다.

F[A] = B 라는 수식을 사용할 것인데, F[A] = B의 의미는 "A번칸 까지 가는데 점프해야 하는 최소 횟수는 B번 입니다." 이다.

#Case1 : 첫 번째 칸 까지 가는데 점프해야 하는 최소 횟수

첫 번째 칸 까지 가는데 점프해야 하는 최소횟수는 몇 번일까 ?? 첫 번째칸은 시작점으로써, 점프를 하지 않더라도 초기에 있는 위치이다. 즉, 0번이된다. F[1] = 0

#Case2 : 두 번째 칸 까지 가는데 점프해야 하는 최소 횟수

두 번째칸까지 가는데 점프해야 하는 최소횟수를 구하기 전에, 두 번째칸 까지 갈 수 있는 경로를 한번 알아보자.

1. 첫 번째 칸 - 두 번째 칸

경로는 이 한가지 밖에 존재하지 않는다.

따라서, 두 번째칸 까지 가는데 점프해야 하는 최소 횟수는 1번이 된다.

F[2] = 1

#Case3 : 세 번째 칸 까지 가는데 점프해야 하는 최소 횟수

마찬가지로, 최소횟수를 구하기 전에, 세 번째 칸 까지 갈 수 있는 경로를 한번 알아보자.

1. 첫 번째 칸 - 두 번째 칸 - 세 번째 칸

이 경우에도, 갈 수 있는 경로가 한 가지 밖에 없다.

왜냐하면, 첫 번째 칸이 가진 숫자가 '1'이라서 최대 한 칸까지밖에 뛸 수 없기 때문에,

첫 번째 칸 - 세 번째 칸 으로 오는 이런 경로는 불가능하다.

따라서, 이 경우에는 점프를 2번 해야만 세 번째 칸 까지 갈 수 있다.

F[3] = 2

#Case4 : 네 번째 칸 까지 가는데 점프해야 하는 최소 횟수

네 번째 칸 까지 갈 수 있는 경로를 한번 알아보자. 지금부터는 간단하게, 첫 번째 칸, 두 번째 칸 이런 말 대신 1번, 2번, 3번.. 등으로 표시하겠다.

1. 1번 - 2번 - 3번 - 4번

2. 1번 - 2번 - 4번

위와 같이 2가지 경로가 존재한다.

위의 2가지 경우 중, 점프를 더 적게하는 경우는 2번 경우로, 점프 횟수가 2번이면 된다.

따라서, F[4] = 2 라는 결과를 얻을 수 있다.

그런데 ! 이제는 여기서 끝내지 말고, 보다 일반적인 상황으로 나타내보자.

먼저, 위의 2가지 경우의 차이점을 한번 살펴보자.

가장 큰 차이점으로는, 1번 경우에는 '3번'을 거쳤지만, 2번 경우에는 '3번'을 거치지 않았다는 차이점이 있다.

반대로 공통점으로는 3번을 거친 1번 경우도, 결국 4번까지 올 수 있고, 3번을 거치지 않은 2번 경우도 결국 4번까지 올 수 있다는 공통점이 있다.

즉 ! 우리는 N번까지 가는데 점프해야 하는 최소횟수를 구하기 위해서, "1 ~ N - 1번 중에서, 점프를 해서 N번에 도달할 수 있는 지점을 찾는다." 라는 것을 하나의 조건으로 생각해 볼 수 있다.

우리가 했던 상황을 위에서 했던 말에 그대로 대입해보면, "4번까지 가는데 점프해야 하는 최소횟수를 구하기 위해서, 1 ~ 3번 중, 점프를 해서 4번에 도달할 수 있는 지점을 찾았고, 그 지점으로는 2번과 3번이 있습니다" 라고 표현할 수 있다.

그럼, 2번이든 3번이든 결국 "한 번만 더 점프하면 4번에 도달"하게 된다. 그럼 ? 이 때 4번까지 가는데 점프해야 하는 쵯소 횟수는 몇번이 될까 ?? 바로, "2번을 갈 때 점프해야 하는 최소횟수 vs 3번을 갈 때 점프해야 하는 최소 횟수" 가 되는 것이다.

다시 한번 정리해보자.

우리는 4번까지 가는데 점프해야 하는 최소 횟수를 구하기 위해서, "한 번만 더 점프하면 4번 지점으로 갈 수 있는 지점인, 2번 지점과 3번 지점을 찾았다. 즉, 2번이든 3번이든 딱 한번만 더 점프를 하면 4번 지점에 도달하게 되는데, 그럼 이 때 4번 지점으로 갈 때, 점프해야 하는 최소 횟수는, 2번을 갈 때 점프해야 하는 최소횟수와 3번을 갈 때 점프해야 하는 최소횟수를 중, 더 적은 횟수 + 1 이 결국 4번으로 갈 때 점프해야 하는 최소횟수 가 되는 것"이다.

말이 복잡해서 그렇지 코드로 한번 살펴보자.

DP[1] = 0;
for (int i = 2; i <= N; i++)
{
    for (int j = 1; j < i; j++)
    {
        if (j + Arr[j] >= i)
        {
            DP[i] = Min(DP[i], DP[j] + 1);
        }
    }
}

본인이 구현한 코드이다.

line1) 에서는 Case1과 같이, "첫 번째 칸 으로 갈 때, 점프해야 하는 최소횟수"를 나타낸 것이다. 0회이다.

line2) 에서 보면, 두 번쨰 칸 ~ N번째 칸 까지 각 칸을 갈 떄, 점프해야 하는 최소횟수를 구하기 위해서 반복문이 돌게 된다.

line4) 에서 보면, i번째 칸에 대해 점프해야 하는 최소 횟수를 구하기 위해서, 1 ~ i - 1 까지의 칸 중에서, "한 번만 더 점프하면 i번 째 칸이 되는 지점"을 찾는 과정이다.

line6) 에서 보면 실제로 그런 조건문이 달려있다.

line8) 에서 보면, 그런 지점 중에서 점프해야 하는 최소횟수가 가장 적은 횟수를 설정해 주는 과정이다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
        DP[i] = 2e9;
    }
}
 
void Solution()
{
    DP[1] = 0;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (j + Arr[j] >= i)
            {
                DP[i] = Min(DP[i], DP[j] + 1);
            }
        }
    }
    if (DP[N] == 2e9) cout << -1 << endl;
    else cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}