Pascal's Travels (feat. 백준, 4620번)

Pascal's Travels
https://www.acmicpc.net/problem/4620

4620번: Pascal's Travels

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	char arr[35][35];
	long long dp[35][35];
	while (1) {
		cin >> N;
		if (N == -1)
			break;
		for (register int i = 1, j; i <= N; ++i)
			for (j = 1; j <= N; ++j)
				cin >> arr[i][j], arr[i][j] -= '0', dp[i][j] = 0;
		dp[1][1] = 1;
		for (register int x = 1, y; x <= N; ++x)
			for (y = 1; y <= N; ++y) {
				if ((x == N && y == N) || (dp[x][y] == 0))
					continue;
				register int dist = arr[x][y];
				register int down = x + dist;
				register int right = y + dist;
				if (down <= N)
					dp[down][y] = dp[down][y] + dp[x][y];
				if (right <= N)
					dp[x][right] = dp[x][right] + dp[x][y];
			}
		cout << dp[N][N] << "\n";
	}
	return 0;
}
// *&)*@*

 

1. 문제는 dp를 이용하여 풀이하는 문제입니다.
2. (1,1)에서 (N,N)까지의 모든 경로를 구할때, (x,y)는 (1,1)에서의 방문 횟수를 저장하고 이후 다시 (x,y)를 거친다면 이전 저장된 방문 횟수를 그대로 사용하게 됩니다.