[BOJ][C++] 백준 1890번: 점프

문제

https://www.acmicpc.net/problem/1890

 

문제 이해

수가 적혀 있는 N×N 게임판에서 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 따라 점프한다.

규칙에 맞게 이동할 수 있는 경로의 개수를 구한다.

 

규칙

1. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다.
2. 0은 종착점을 의미한다.
3. 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로만 이동 가능하다.
4. 한 번 점프할 때 방향을 바꿀 수 없다. 오른쪽으로 또는 아래로 점프를 하는 두 경우만 존재한다.

 

문제 풀이

🔍 접근

각 칸마다 현재 칸까지의 경로의 개수를 저장한다.

 

💡 Dynamic Programming

칸에 적힌 수만큼 이동해서 해당 칸까지의 경로의 개수를 저장한다.

• 첫 번째 칸(경로의 개수 1)부터 시작한다.
• 오른쪽으로 점프한다:
  다음 열 = j + v[i][j]
  dp[i][다음 열] += dp[i][j](이전 칸까지의 경로의 개수)
  
• 아래로 점프한다:
  다음 행 = i + v[i][j]
  dp[다음 행][j] += dp[i][j]
  

 

🚨

• 경로의 개수의 범위(<=2^63-1)를 고려하여 자료형(long long)을 설정한다.
• 인덱스가 게임판 범위를 넘지 않도록 한다. (< n)
• 마지막 칸에서 경로가 중복 계산되는 것을 방지한다. (dp[i][j] += dp[i][j] 가 되는 경우)

 

코드

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

ll countRoute(int n, vector<vector<int>> &v)
{
    vector<vector<ll>> dp(n, vector<ll>(n, 0));
    
    dp[0][0] = 1;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!v[i][j])
                continue;
                
            int nr = i + v[i][j];
            int nc = j + v[i][j];
            
            if (nc < n)
                dp[i][nc] += dp[i][j];
            if (nr < n)
                dp[nr][j] += dp[i][j];
        }
    }

    return dp[n - 1][n - 1];
}

int main()
{
    int n;
    vector<vector<int>> v;
    
    cin >> n;
    v.assign(n, vector<int>(n, 0));
    
    for(int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> v[i][j];
            
    cout << countRoute(n, v);

    return 0;
}