문제
계단을 오르는 횟수와 계단 개수가 모두 N이므로, 이 문제를 각각 2가지 선택지로 분기해서 풀게 되면 결국 시간초과가 나게 되어있다. 따라서 더 효율적으로 계단을 올라갈 방법을 찾아야 했다. 처음에는 제대로 생각이 나지 않았다. 정확히 k번을 맞춰 N번째 계단에 오르기 위해서는 최솟값을 구하는 것도 아니기 때문이다. 그러다가 질문을 봤는데 여기서 깨달았다.
지팡이로 순간이동하는 경우, Math.floor(i/2) 로 순간이동을 한다.
하지만 이 i가 1인 경우?
무한 제자리 순간이동이 가능해진다…!(두둥)
그렇기 때문에 결국 n번째 계단을 k횟수 안에 도달만 한다면 티배깅하듯이 제자리 순간이동하다가 가면 된다!
따라서 n까지 도달하는 최소횟수를 구하면 된다. 이 부분은 일반적인 탐색이 아닌 dp를 이용하여 더 효율적으로 풀 수 있다.
모든 배열을 Infinity값으로 먼저 초기화 시킨 후 배열을 돌면서
현재 위치에서 앞으로 갈 수 있는 경우(i+1<=n)
- 현재 위치에서 한칸 앞으로 갔을 때의 횟수와 한칸 앞의 최소횟수가 있는 경우
현재 위치에서 순간이동 가능한 경우 (
i+Math.floor(i/2)) - 현재 위치에서 한칸 앞으로 갔을 때의 횟수와 뛰어넘을 때 있는 위치에서 가지는 최소횟수중에 하나 골라서 +1
이렇게 값을 업데이트 시키면 된다.
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "inputs.txt";
const [n, k] = require("fs")
.readFileSync(INPUT_FILE)
.toString()
.trim()
.split(" ")
.map(Number);
const dp = Array.from({ length: n + 1 }, () => Infinity);
dp[0] = 0;
for (let i = 0; i < n; i++) {
if (i + 1 <= n) dp[i + 1] = Math.min(dp[i + 1], dp[i] + 1);
if (i + Math.floor(i / 2) <= n)
dp[i + Math.floor(i / 2)] = Math.min(
dp[i] + 1,
dp[i + Math.floor(i / 2)] + 1
);
}
dp[n] <= k ? console.log("minigimbob") : console.log("water");
제자리뛰기하는 경우는 생각도 못했는데 이 부분도 이제 잘 봐야겠다;;