[C/C++ 백준 1890번] 점프 (Silver 2)

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

1890번: 점프

코드업 1099번이 생각나는 문제이다. 해당 문제도 재귀함수로 풀었었기 때문에, 일단 바로 재귀함수를 써보았다.

---

#include <cstdio>
int func(int arr[][101], int x, int y, int N){
	int ans=0;
	if(x==N && y==N)
		return 1;
	if(x+arr[x][y]<=N)
		ans += func(arr, x+arr[x][y], y, N);
	if(y+arr[x][y]<=N)
		ans += func(arr, x, y+arr[x][y], N);
	return ans;
	
}
int main(void){
	int N;
	scanf("%d",&N);
	int game[101][101]={};
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf(" %d",&game[i][j]);
		}
	}//타일 생성
	int ans = func(game, 1, 1, N);
	printf("%d",ans);
}

 

 

 

---

당연하게도 시간초과가 뜬다. 다이나믹 프로그래밍이라는 카테고리에 맞게 풀어야 조건을 만족시킬 수 있을 것 같다. 규칙 자체는 어렵지 않다. 제일 오른쪽 아래 칸을 1로 채우고, dp[i][j] += dp[i+game[i][j]][j] + dp[i][j+game[i][j]] 이런식으로 오른쪽으로 갔을 때의 경로와 아래로 갔을 때의 경로를 더한 것을 새롭게 dp에 채우면 된다.

2	3	3	1
1	2	1	3
1	2	3	1
3	1	1	0

 

3	1	1	0
3	1	0	0
2	1	0	1
1	1	1	1

 

위가 game의 배열, 아래가 dp의 배열이다. 이런식으로 for문을 두번 돌려, dp를 역순으로 채워 나간다.

---

#include <cstdio>
int func(int arr[][101], int x, int y, int N){
	int ans=0;
	if(x==N && y==N)
		return 1;
	if(x+arr[x][y]<=N)
		ans += func(arr, x+arr[x][y], y, N);
	if(y+arr[x][y]<=N)
		ans += func(arr, x, y+arr[x][y], N);
	return ans;
	
}
int main(void){
	int N;
	scanf("%d",&N);
	int game[101][101]={};
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			scanf(" %d",&game[i][j]);
		}
	}//타일 생성
	int ans = func(game, 1, 1, N);
	printf("%d",ans);
}

---

해결!