[JavaScript/DP] 백준 실버 1 : 1890 - 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

---

📌 작성한 코드 

// 1890
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const board = input.map((str) => str.split(" ").map(Number));

const dp = Array.from({ length: N }, () => new Array(N).fill(BigInt(0)));

dp[0][0] = BigInt(1);

for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        const cur = board[i][j];

        if (i === N - 1 && j === N - 1) {
            break;
        }

        if (cur === 0) {
            dp[i][j] = BigInt(0);
            continue;
        }

        if (j + cur < N) {
            dp[i][j + cur] += dp[i][j];
        }

        if (i + cur < N) {
            dp[i + cur][j] += dp[i][j];
        }
    }
}

console.log(dp[N - 1][N - 1].toString());

 

📌 설명 

dp[i][j] = (i,j) 좌표에 도달할 수 있는 경로의 수 

- 현재 위치에서 오른쪽과, 아래쪽으로 이동할 수 있는 칸의 dp에 현재까지의 경로의 개수를 더해준다. 

- 점프 가능 값이 0인 경우에는 다음 위치로 점프가 불가능하므로 값을 0으로 초기화 해준다.

 

* 주의 : 가능한 경로의 수가 매우 큰 값이므로 BigInt를 사용해야 한다.

 

 

✅ 성공