백준 1890번 [점프](C++)-yes6686- 티스토리

백준 문제 풀이: 1890 [점프]

---

문제 링크: https://www.acmicpc.net/problem/1890

문제 설명:

n × n 크기의 게임판이 주어집니다. 각 칸에는 수가 하나 적혀 있으며, 이 숫자는 그 칸에서 점프할 수 있는 거리입니다. (오른쪽 또는 아래쪽으로만 점프 가능)

맨 왼쪽 위에서 출발하여 맨 오른쪽 아래까지 도달하는 방법의 수를 구하는 문제입니다.

입력:

• 첫째 줄에 n (4 ≤ n ≤ 100)이 주어집니다.
• 둘째 줄부터 n개의 줄에 걸쳐 게임판의 정보가 주어집니다. 각 칸의 숫자는 0 이상 9 이하의 정수입니다.

출력:

• 맨 왼쪽 위에서 출발하여 맨 오른쪽 아래로 도달하는 방법의 수를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

long long dp[101][101];
int board[101][101];

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

    int n;
    cin >> n;

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

    dp[0][0] = 1; // 시작점에서의 경로 수는 1

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == n - 1 && j == n - 1) continue; // 마지막 도착점
            int jump = board[i][j];
            if (jump == 0) continue; // 이동 불가
            if (i + jump < n) dp[i + jump][j] += dp[i][j]; // 아래로 이동
            if (j + jump < n) dp[i][j + jump] += dp[i][j]; // 오른쪽으로 이동
        }
    }

    cout << dp[n - 1][n - 1] << '\n';
    return 0;
}

예제

입력:
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

출력:
3

---

코드 설명

• 동적 프로그래밍 배열:
  • dp[i][j]는 (i, j) 위치에 도달하는 방법의 수를 저장합니다.
• 점프 계산:
  • 현재 위치의 점프 길이만큼 아래쪽 또는 오른쪽으로 이동합니다.
  • 이동 가능한 위치에 도달 방법의 수를 누적합니다.

시간 복잡도

• 게임판의 크기가 n × n일 때, 모든 칸을 한 번씩 탐색하므로 시간 복잡도는 O(n²)입니다.
• n ≤ 100이므로 충분히 빠르게 동작합니다.

---

결과

코드는 주어진 게임판에서 맨 오른쪽 아래로 도달하는 모든 경로를 정확히 계산합니다. DP를 활용한 효율적인 구현으로, 문제의 제약 조건 내에서 잘 작동합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!