BOJ 28069 - 김밥천국의 계단

July 23, 2023

항상 $i=0$ 에서 2번 연산을 쓰면 연산을 쓸모없게 만들 수 있으므로 $K$ 번안에 $N$ 에 도달할 수 있기만 하면 항상 가능한 경로를 만들 수 있다.

DP로 풀어주면 된다.

void solve() {
   int n, k;
   cin >> n >> k;
   vi dp(n + 1, 1e9);
   dp[0] = 0;
   for (int i = 0; i < n; i++) {
      mina(dp[i + 1], dp[i] + 1);
      int m = i + i / 2;
      if (m <= n)
         mina(dp[m], dp[i] + 1);
   }
   cout << (dp[n] <= k ? "minigimbob" : "water");
}