[C++] 백준 1890번 점프

 

다이나믹 프로그래밍 문제입니다.

DFS나 BFS로도 풀 수 있지만 시간초과가 날 가능성이 큽니다.

 

n*n 배열에서 최종 목적지까지 갈 수 있는 경우의수를 구하는 문제입니다.

각 배열의 값만큼 점프해서 오른쪽이나 밑으로만 이동할 수 있습니다.

 

 

for문을 두번 돌려서 진행합니다.

 

처음 시작 위치를 1로 두고

오른쪽과 아래에 점프 가능한 곳에 현재 숫자를 더해줍니다.

 

다음 값의 위치에서 숫자가 0이 아니면 

점프가 가능한 곳에 현재 숫자를 더해줍니다.

 

이를 반복하면 최종위치에는 도착한 경우의 수가 쌓이게 됩니다.

 

if (memo[i][j] == 0) {                
	continue;
}

 // 위치에 아무도 점프한적 없는 경우

if (i == n - 1 && j == n - 1) {    
    break;
}

//  마지막 위치에 도착했을 경우 종료

if (x < n) {                              
    memo[x][j] += memo[i][j]; 
}

 // x가 n을 벗어나지 않으면 (x는 i+점프값)

if (y < n) {                               
    memo[i][y] += memo[i][j];
}

// y가 n을 벗어나지 않으면 (y는 j+점프값)

 

#include <iostream>
using namespace std;

void solve()
{
 	int map[110][110];
 	long long int memo[110][110];
 	int n;

 	cin >> n;

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

 	for (int i = 0; i < n; ++i) {
 		for (int j = 0; j < n; ++j) {
 			int x = i + map[i][j];
 			int y = j + map[i][j];

 			if (memo[i][j] == 0) {
 				continue;
 			}
 			if (i == n - 1 && j == n - 1) {
	 			break;
	 		}
 			if (x < n) {
 				memo[x][j] += memo[i][j];
 			}
 			if (y < n) {
 				memo[i][y] += memo[i][j];
 			}
 		}
 	}
 	cout << memo[n - 1][n - 1] << endl;
}

int main(int argc, char *argv[])
{
 	solve();

	return 0;
}