C++(씨쁠쁠)(cplusplus)-백준(baekjoon)(BaekJoon)코딩 1890번:점프 답

d[i][j] = (i,j)로 가는 경로의 개수

a[i][j] = 입력

->먼저 i,j로 올 수 있는 발판을 찾아야합니다 : k이용

1.왼쪽에서 오른쪽으로 오는 방법 : 

d[i][j] += d[i][k] (a[i][k] + k == j, 0 <= k < j)

2.위에서 내려오는 방법 : 

d[i][j] += d[k][j] (a[k][j] + k == i, 0 <= k < i)

d[n][n] = (1방법 + 2방법)

현재위치로 가려면 그 전 위치에서 갈 수 있는 방법을 찾아서 그 가짓수를 모두 더해야 하는 문제입니다.

#include <iostream>
using namespace std;
int a[100][100], n;
long long d[100][100];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    d[0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (i == 0 && j == 0) { continue; }
            for (int k = 0; k < j; k++)//방법1
                if (k + a[i][k] == j)
                    d[i][j] += d[i][k];
            for (int k = 0; k < i; k++)//방법2
                if (k + a[k][j] == i)
                    d[i][j] += d[k][j];
        }
    }
    cout << d[n-1][n-1] << '\n';
}