[백준]1890번: 점프

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

1890번: 점프

 

---

 

처음에는 방문했던 점을 큐에다가 넣어가면서 단순 탐색을 했었는데 자꾸 메모리 초과가 됐다

찾아보니까 단순탐색, dfs, bfs로 풀면 시간이나 메모리 초과가 나는 문제였다

그래서 dp로 풀었음!!

 

#include <iostream>

using namespace std;

int n;
int arr[101][101];
long dp[101][101]; //경로의 개수는 최대 2^63 - 1 까지다. (int범위 초과)

int main(){
	
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>arr[i][j];
		}
	}
	if(n==1 || arr[0][0]==0) {	//n이 1이거나 첫칸에서 점프를 할 수 없으면 정답은 0
		cout<<"0"; return 0;}
		
	dp[0][0]=1;
	
	int path=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int jump = arr[i][j];
			if(i==n-1 && j==n-1) continue;
			if(i+jump<n) dp[i+jump][j] += dp[i][j];
			if(j+jump<n) dp[i][j+jump] += dp[i][j];
			}
	}

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