[BaekJoon, C++] 1890번 - 점프

 

1890번: 점프

 

 

#include <iostream>

using namespace std;

int n;

int map[100][100];

long long dp[100][100];


int main(){

  cin>>n;

  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin>>map[i][j];
    }
  }

  dp[0][0] = 1;

  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 right =  i + map[i][j];
      int down = j + map[i][j];

      if(right < n) dp[right][j] += dp[i][j];
      if(down < n) dp[i][down] += dp[i][j];



    }
  }
  cout<<dp[n-1][n-1];


  



}

 

 

오른쪽, 아래로밖에 못 움직인다. ( 0 , 0 ) 까지 갈 수 있는 경로를 1로 설정한다.

map ( i , j ) 에서의 값 + 인덱스 를 통해 오른쪽, 아래로 움직일 수 있는 거리를 설정한다.

map 크기 안에 들어오면 dp를 갱신해준다.

 

가능한 경로 수의 범위를 보지 못하고 처음에 dp를 int로 선언해줬다가 퍼센트 다 올라갔는데 틀리길래

문제를 다시 읽어보니 경로 수가 2^63 -1 보다 같거나 작다고 한다.

그래서 long long 으로 바꿔주었더니 맞았다.

문제를 똑바로 읽자.