백준 1890 점프

혹시 백준에서 채점 돌렸는데 잘 맞추다가 후반부에서 오답나오신분이시라면

결과 출력을 long long으로 했는지 체크하세용

저도 첨에 long long 박아놨다가 막판 출력을 int로 하는 바람에 형번환 되서 한번 틀렸네요 ㅎㅎ

BFS문제 풀려고 BFS 눌렸는데 왠 DP문제가 떠서 그냥 풀었다

r만큼 떨어져있는 노드에서 r만큼의 점프가 가능한지 검사하여

가능할 경우 해당 노드까지 도달할 수 있는 경로의 수를 더하는 알고리즘이다

점화식은 아래와 같다.

D[i][j] = D[i-r][j] + D[i][j-r], r = [1..9] (if arr[i-r][j] == r, arr[i][j-r] == r)

DP는 점화식만 세우면 빠르게 모델링하여 풀수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

long long memo[101][101];
int arr[101][101];
int N;

long long calc(int i, int j) {
	for (int r = 1; r < 10; r++) {
		if (arr[i - r][j] == r && i - r >= 0) {
			if (memo[i - r][j] != 0) {
				memo[i][j] += memo[i - r][j];
			}
			else {
				memo[i][j] += calc(i - r, j);
			}
		}
		if (arr[i][j - r] == r && j - r >= 0) {
			if (memo[i][j - r] != 0) {
				memo[i][j] += memo[i][j - r];
			}
			else {
				memo[i][j] += calc(i, j - r);
			}
		}
	}
	return memo[i][j];
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			memo[i][j] = 0;
		}
	}

	memo[0][0] = 1;

	cout << calc(N - 1, N - 1) << endl;

	return 0;
}

내용