[ 백준 1890 ] 점프 (C++)

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

( 문제 바로가기 )

[ 문제풀이 ]

1) 본인은 이 문제를 풀 때 크게 2개의 2차원 배열을 사용하였다.

   하나는, 맵을 입력받는 int형 2차원 배열 MAP[][]을 사용했고, 또 하나는, 경로의 갯수를 저장하는 DP[][] 배열을 사용

   하였다.

   DP[a][b] = c 의 의미는 "(a, b)까지 올 수 있는 경로의 수는 c개 입니다" 가 된다.

  

   문제를 구현하는 방법은 크게 어렵지 않다. 현재 정점에서 오른쪽 혹은 아래쪽으로 이동하면서, 해당 정점의 DP[] 같을

   더해주면 된다.

2) 또한, 시간을 줄이기 위한 방법으로는 DP[][] = 0 인 좌표는 그냥 지나쳐 버리는 방식이 있다.

   이 부분에 대해서 구체적으로 알아보자.

  

   위의 왼쪽 표는 예제입력1을 그대로 가져온 것이고, 오른쪽 표는 DP[][]를 표로 나타낸 것이다. 시작점은 무조건 거쳐야 하

   기 때문에 처음에 DP[0][0] = 1 로 시작한다.

   이제 (0, 0)에서 오른쪽 or 아래쪽으로 가보자. 그렇게 되면, 파랑색으로 표시된 두 개의 점으로 가게 될 것이다.

   두 개의 점으로 가게 되면, 오른쪽 표에서 파랑색으로 표시된 두 개의 0은 1로 값이 바뀌게 될 것이다.

   그 상태에서, (0, 1) 좌표에 집중하자. 우리는 과연 (0, 1)좌표에 대한 어떠한 계산을 해줘야 할까? 해줄 필요가 없다.

   어차피 가지 않는 경로이기 때문에 지나치면 된다. 즉 DP[][] =0 인 좌표에 대해서는 그냥 지나쳐 주면 된다.

   이런식으로 모든 경로를 다 계산 후, DP[N-1][N-1]의 값을 출력해주면 정답이다 !

[ 소스코드 ]

#include<iostream>
 
typedef long long ll;
#define endl "\n"
#define MAX 100
using namespace std;
 
int N;
int MAP[MAX][MAX];
ll DP[MAX][MAX];
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    DP[0][0] = 1;
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (DP[i][j] == 0 || (i == N - 1 && j == N - 1)) continue;
            
            int Value = MAP[i][j];
            int Down = Value + i;
            int Right = Value + j;
 
            if (Down < N) DP[Down][j] = DP[Down][j] + DP[i][j];
            if (Right < N) DP[i][Right] = DP[i][Right] + DP[i][j];
        }
    }
    cout << DP[N - 1][N - 1] << 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;
}