[백준][1890번] 점프

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

1890번: 점프

 

 

풀이과정

1. dp로 풀었다.

 

2. 현재 발판의 값을 v라고 했을 경우 아래와 같은 답을 구 할 수 있었다.

 

dp[y][x] = dp[y+v][x] + dp[y][x+v] 라는 점화식을 구할 수 있다.

 

dp[n][n]을 도착 할 경우 1을 반환해주면 중복처리 없이 답을 구 할 수 있었다.

 

*dp 공부전엔 bfs로 시간초과가 발생했던 문제였다..

 

 

 

소스코드

#include<stdio.h>
#include<string.h>
typedef unsigned long long ull;
int map[101][101];
ull dp[101][101];
int n;
ull solution(int x, int y)
{
	if (x == n - 1 && y == n - 1)
		return 1;
	
	if (dp[y][x] != -1)
		return dp[y][x];
	
	int num = map[y][x];
	dp[y][x] = 0;
	if (y + num < n) {
		dp[y][x] += solution(x, y + num);
	}
	if (x + num < n) {
		dp[y][x] += solution(x + num, y);
	}
	return dp[y][x];
}

int main()
{
	scanf("%d\n", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	memset(dp, -1, sizeof(dp));
	solution(0, 0);
	printf("%llu\n", dp[0][0]);
}