[PS金俊-5.9]1890号:ジャンプ

問題情報

コメント

ソースコード

<タワータイプ>

#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>

#define MAX 101

using namespace std;

int maps[MAX][MAX];
long long int dp[MAX][MAX];
int N;

// r, c는 좌표 / n은 적힌 숫자
long long int jump(int r, int c, int n) {
	// cout << "(" << r << "," << c << ") n: " << n << endl;
	// base case
	if (r == N - 1 && c == N - 1) return 1;
	if (n == 0 || r > N - 1 || c > N - 1) return 0;

	// memoization
	if (dp[r][c] != -1) return dp[r][c];

	long long int result = jump(r + n, c, maps[r + n][c]) + jump(r, c + n, maps[r][c + n]);
	dp[r][c] = result;
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	fill(&dp[0][0], &dp[MAX - 1][MAX], -1);
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int x;
			cin >> x;
			maps[i][j] = x;
		}
	}
	dp[N - 1][N - 1] = 1;

	// 스타트: jump(0, 0, map[0][0]);
	cout << jump(0, 0, maps[0][0]);

}

<起動方式>-by zzoni

#include <iostream>
#include <algorithm>
using namespace std;

int map[101][101];
long long int dp[101][101]; // dp에 경로개수 저장!
int N;

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;

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

    dp[0][0] = 1; // 시작점은 무조건 1번 거치니까

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (map[i][j] != 0 ){ // 종착지가 아니라면
                //아래로
                if (i + map[i][j] < N) {
                    dp[i + map[i][j]][j] += dp[i][j];
                }
                //오른쪽으로
                if (map[i][j] != 0 && j + map[i][j] < N) {
                    dp[i][j + map[i][j]] += dp[i][j];
                }
            }
        }
    }

    cout << dp[N - 1][N - 1];

    return 0;
}