[백준] 1890_점프 (C++)

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

1890번: 점프

 

[규칙]

1. 오른쪽과 아래쪽만 이동 가능
2. 칸에 적혀져 있는 칸만큼 이동
3. 0이 나오면 못 감
4. 경로의 개수는 2^63-1보다 작거나 같음
5. 경로의 개수 구해라

 

[실패 원인]

1. 문제를 제대로 안 읽었다. (최단기 거리인 줄,, )
2. 제일 간단한 DFS로 푸니깐 시간 초과가 났다.
3. 경로의 개수가 2^63-1보다 작거나 같다 == int형으로는 안된다. 

 

[풀이 설명]

DFS로 푼 것이랑 원리는 비슷한데

반복문을 통해 풀었다. 

• 따른 배열을 만들어서
• route [0][0] 배열에는 1을 저장한다. 
• 각 행열을 다 지나치면서
  • 0이 아니거나, 배열 만든 것(route)이 0이 아니면
  • 가로, 세로에 각 칸에 있는 칸만큼 더해서 더한다. 

 

 

이렇게 경로를 저장할 수 있다. 

 

 

 

 

 

 

[소스코드]

#include<iostream>
using namespace std;

int N;
int input_array[101][101];
long long route[101][101] = { 0 };

int main() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> input_array[i][j];
	
	route[0][0] = 1;
	for(int row = 0; row<N; row++)
		for (int col = 0; col < N; col++) {
			if (input_array[row][col] != 0 && route[row][col]!= 0) {
				if (row + input_array[row][col] < N)
					route[row + input_array[row][col]][col] += route[row][col];
				if (col + input_array[row][col] < N)
					route[row][col + input_array[row][col]] += route[row][col];
			}
		}
	cout << route[N-1][N-1];
	return 0;
}