[JavaScript] 백준 13549번 - 숨바꼭질 3

[문제]

[풀이]

수빈이가 동생을 찾아서 이동할 수 있는 방법은 2가지가 있습니다.

• 1초 동안 -1 칸 or +1 칸 이동
• 0초 동안 순간이동하여 X2칸 이동

따라서 규칙적으로 이동하는 것을 보고 DP를 활용하여 풀이하였습니다.

 

1. 수빈이 위치 N보다 작은 칸으로는 순간이동이 불가능해서 항상 1초가 걸려 -1칸씩 이동해야합니다.

• N보다 작은 위치는 0에서 1초씩 시간을 증가시켜 각 dp 배열의 위치 인덱스에 시간을 저장

2. 수빈이 위치 N을 0초로 시작해서 N보다 큰 칸으로 이동하는 경우는 걷기와 순간이동 2가지가 있습니다. 따라서 현재 위치를 X라고 했을때, X위치로 이동할 수 있는 경우는 2가지가 있습니다.

• X-1에서 +1칸 걸어온 경우 : 1초의 시간이 걸림 => dp[X-1] + 1
• X/2 칸에서 순간이동한 경우 : 0초의 시간이 걸림 => dp[X/2] (X의 값이 짝수인 경우에만 가능!!)

따라서 2번의 경우 점화식을 세우면 dp는 dp[X-1] + 1 와 dp[X/2] 중 더 작은 값이 됩니다.

 

3. dp[X/2]로 X의 위치가 갱신되면, X보다 작은 값들도 다시 갱신해주어야 합니다.

• dp[X/2]가 선택된 경우, X부터 X/2까지 -1칸씩 내려가며 "dp[X/2] + 내려간 칸수"가 해당 칸의 dp값보다 작다면 갱신

최종적으로 dp[K]의 값을 출력해줍니다.

 

*처음에 dp를 K까지 구해주었는데, K보다 큰수에서 -1칸씩 내려온 경우에서 최소값이 구해질 수도 있다는 것을 알고 범위를 K+N으로 확장시켜주었습니다.

 

 

 

예시 1번을 살펴보자면 N=5이고 K=17일때 과정은 다음과 같습니다.

1. 0~5 까지 구하기

dp = [5,4,3,2,1,0]

 

2. 6~22 까지 구하기

dp[6] = dp[5] + 1 = 1 (dp[3]의 값은 2이기 때문에 1로 갱신)

dp[7] = dp[6] + 1 = 2 (홀수이니까 전칸 + 1)

dp[8] = dp[4] = 1 (dp[7] + 1 = 3으로 1보다 큼)

...

 

 

 

이런식으로 구해나가면 dp[K] = 2 를 구할 수 있습니다.

 

[코드]

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split('\n');

const [N, K] = input[0].split(" ").map(Number);
const len = K + N;

let dp = Array.from({length: len}, (_, i) => -1);

for(let i=0;i<=N;i++) {
    dp[i] = N-i;
}

for(let i=N+1;i<=len;i++) {
    const num = dp[i-1] + 1;
    const divNum = i/2;
    if(divNum >= 0 && i % 2 == 0 && dp[divNum] < num) {
        dp[i] = dp[divNum];

        // 밑에 애들도 갱신
        for(let j=i-1;j>=divNum;j--) {
            if(dp[j+1] + 1 < dp[j]) {
                dp[j] = dp[j+1] + 1;
            } else {
                break;
            }
        }
    } else {
        dp[i] = num;
    }
}

console.log(dp[K]);