백준 1890 - 점프 (c++)

백준 1890 - 점프

문제 링크

생각 및 접근

• 문제를 이해하는 것이 우선이였다. 내가 위치하는 곳의 값만큼 오른쪽이나 아래로 이동할 수 있다는 것이다.
• 동적 프로그래밍을 이용해 풀었는데, dp[i][j]에 (i, j)로 왔을 때 경로의 수를 저장하였다.

• 

  • 주황색 부분을 검사하는 코드가 다음과 같다. 주황색 부분을 돌면서, 주황색 부분에 든 숫자 arr[][]와 주황색과 [i][j]까지의 거리가 같다면, 주황색에서 [i][j]로 이동할 수 있다는 것을 알게 된다. 따라서, dp[i][j] += dp[k][j];를 해주면, 주황색 부분까지 가는 경우의 수를 더해준다는 의미가 되겠다.

      for (int k = 1; k < i; k++) {
          if (arr[k][j] == i - k) {
              dp[i][j] += dp[k][j];
          }
      }

  • 초록색 부분을 검사하는 코드가 다음과 같다. 초록색 부분을 돌면서, 주황색 부분에 든 숫자 arr[][]와 초록색과 [i][j]까지의 거리가 같다면, 초록색에서 [i][j]로 이동할 수 있다는 것을 알게 된다. 따라서, dp[i][j] += dp[i][k];를 해주면, 초록색 부분까지 가는 경우의 수를 더해준다는 의미가 되겠다.

      for (int k = 1; k < j; k++) {
          if (arr[i][k] == j - k) {
              dp[i][j] += dp[i][k];
          }
      }

코드

#include <bits/stdc++.h>
using namespace std;

int n;
long long arr[101][101], dp[101][101];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k < i; k++) {
                if (arr[k][j] == i - k) {
                    dp[i][j] += dp[k][j];
                }
            }
            for (int k = 1; k < j; k++) {
                if (arr[i][k] == j - k) {
                    dp[i][j] += dp[i][k];
                }
            }
        }
    }

    cout << dp[n][n];
}

채점 결과