[Baekjoon] 1890번: 점프

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

1890번: 점프

 

---

 

문제 해결 과정

착안

가장 왼쪽 위의 칸에서 시작하여 이동할 때, 각 칸마다 오른쪽 또는 아래쪽으로 이동할 수 있는 두 가지의 경우가 있기 때문에 재귀를 통해 문제를 해결하면 문제에 따라 최대 지수 시간의 시간 복잡도($O(2^n)$)를 나타내게 될 수 있으므로, 이동할 수 있는 경우의 수를 누적하여 계산하는 동적계획법(dynamic programming)에 기반하여 문제를 해결하고자 하였다.

 

구현

동적계획법을 통해 경우의 수를 누적하여 저장할 배열을 선언하고, 시작 지점의 경우의 수를 1로 초기화하여 반복문을 통해 문제를 해결하였다. 반복문 내에서 주의할만한 점은 $i, j = N$ 일 때(즉, 도착 지점인 경우), 해당 위치에 적혀있는 수가 0이므로

DP[$i$ + 0][$j$] += DP[$i$][$j$];

DP[$i$][$j$ + 0] += DP[$i$][$j$];

이 되어 도착 지점까지 이동 가능한 경로의 수가 추가적으로 2 번 더 더해지므로 이를 별도로 처리해야 한다는 점이다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Map[110][110];
unsigned long long DP[110][110];

int main()
{
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> Map[i][j];

	DP[1][1] = 1;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			if (int movement = Map[i][j])
			{
				DP[i + movement][j] += DP[i][j];
				DP[i][j + movement] += DP[i][j];
			}

	cout << DP[N][N];
	return 0;
}

 

실행 결과