[백준_1890] 점프 ( DP - 자바스크립트 )

문제 

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

1890번: 점프

How to Solve ?

 

[1] DP

 

최단거리를 찾는 경우는 BFS를 출력 할 때 카운트를 증가 시켜서 그 값을 map의 마지막 자리에 놓는 식의 풀이가 많았는데, 점프라는 문제는 최종 거리인  Map[n-1][n-1]에 갈 수 있는 경우의 수를 출력 하는 문제였다.

 

1) 어떻게 경우의 수를 얻어 낼 수 있을까?

기존의 BFS는 갈 수 있는 길과, 갈 수 없는 길을 숫자를 통해 구별하여 1로만 가거나 0 인지만 확인을 하면 되는 반면에, 이 문제에서는 지형을 점프하면서 가며 이동한다.

 

그렇다면 어떻게 얻어 낼 수 있을까? 생각해보면, 기존의 값을 변경하는 것이 아니라, DP라는 배열을 만들어 해결 할 수 있다.

 

const dp = [
  [1, 0, 0, 0], 
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
];

다음과 같이 dP 배열을 만들고 이동하는 경우마다 1을 추가 해준다고 하면, 최종 지점은 여러 개의 1이 도착 할 것이고, 그 값이 최종 지점에 도달 가능한 경우의 수가 될 것이다.

 

const dp  = [ 
  [ 1, 0, 1, 0 ],
  [ 0, 0, 0, 0 ],
  [ 1, 1, 0, 1 ],
  [ 1, 0, 1, 3 ]
]

 

최종 코드

 

function solve() {

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      
      if (i === N - 1 && j === N - 1) {
        count += 1;
        break;
      }

      let cur = map[i][j];
	
      // 범위를 벗어 나지 않으면
      if (i + cur < N) {
        dp[i + cur][j] += dp[i][j];
      }

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

let count = 0;
const N = 4;

const map = [
  [2, 3, 3, 1],
  [1, 2, 1, 3],
  [1, 2, 3, 1],
  [3, 1, 1, 0],
];

const dp = [
  [1, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0],
];

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