백준 1890 : 점프 c++

코드

#include <iostream>

using namespace std;

int N;
long long dp[101][101];
int map[101][101];

		

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(map[i][j] == 0) continue;
			else{
				if(i+map[i][j] < N) dp[i+map[i][j]][j] += dp[i][j];
				if(j+map[i][j] < N) dp[i][j+map[i][j]] += dp[i][j];	
			}	
		}
	}
	cout << dp[N-1][N-1];
	return 0;
}

알게된점

처음에는 상하좌우로 이동한다고 생각했는데,

문제를 잘 읽어보니 그냥 하 우로만 움직이면 된다.

어렵지않게 알고리즘을 짤 수 있다.