99클럽 코테 스터디 19일차 TIL - 김밥천국의 계단 (DP)

문제: https://www.acmicpc.net/problem/28069
알고리즘 분류: 너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

문제 정의

최대 K번의 행동으로 N번 계단에 도달할 수 있는가
N번 계단에 도달하는 데 필요한 최소 행동 수가 K 이하인가

DP접근법

각 위치마다 도달하는 데 필요한 최소 행동 수만 기록하면 되고,
마지막에 dp[N] ≤ K인지만 확인

코드

const fs = require('fs');
const [N, K] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);

const dp = new Array(N + 1).fill(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);
  }

  const jump = i + Math.floor(i / 2);
  if (jump <= N) {
    dp[jump] = Math.min(dp[jump], dp[i] + 1);
  }
}

console.log(dp[N] <= K ? 'minigimbob' : 'water');