[백준 28069번] 김밥천국의 계단 (C++)

문제링크 : https://www.acmicpc.net/problem/28069

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main() 
{
    int N, K;
    cin >> N >> K;
    vector<int>dp(N+1, INT_MAX);
    dp[0]=0;
    for(int i=0; i<=N; i++)
    {
        if(i+1 <=N) dp[i+1] = min(dp[i+1], dp[i]+1);
        if(i+i/2 <=N) dp[i+i/2] = min(dp[i+i/2], dp[i]+1);
    }

    cout << (dp[N] <= K ? "minigimbob" : "water"); 

    return 0;
}

 

이동 방법은 문제에 주어진 것처럼 2가지이다.

(계단 한 칸 이동 or i+i/2 번째 계단으로 순간이동)

따라서 해당 행동을 토대로 dp 식을 구성해준다.

 

먼저 dp는 최대값으로 초기화하고, 최소값을 통해 값을 갱신해나간다.

이때 i+1과 i+i/2의 값이 N이 초과하지 않도록 범위를 제한해주어야 한다.

둘 다 행동이 하나이므로 dp[i]+1과 비교하게 되며, N까지 모두 갱신한 이후 dp[N]<=K의 조건을 검토후 맞는 값을 출력하면 된다.

 

여기서 주의할점이 dp[N]==K가 아닌 dp[n]<=K인 점이다.

그 이유는 i+i/2의 경우 0번째라 하면 값이 0으로, 0번째에서 행동을 마음대로 하며 K번째 도달에 대한 값을 조정할 수 있다.

따라서 K번째 이하만 되어도 0번째에서 부족한 만큼 지팡이로 현위치로 원하는 만큼 순간이동하고 출발하면 K번째에 도달 가능하므로, dp[n]<=K일 때 가능하다는 점을 염두에 두어야 한다.