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

https://www.acmicpc.net/problem/28069

생각 흐름

• i번째까지 가는 동안 걸리는 최단 경로 형태로 dp 알고리즘을 통해 푸려고 했는데 막상 하려고 보니 딱 K번째에 맞춰야 한다는 조건을 보았다.
• 0과 1의 경우 순간이동 시에 항상 같은 자리를 반복하는 것을 깨닫고, 만약 dp[N]의 값이 K보다 커도 0과 1에서 이동 횟수를 소모하면 되니까 dp[N]의 값이 K보다 크거나 같으면 minigimbob을 출력하도록 했다.
• 점화식은 dp[i+1] = min(dp[i+1], dp[i]+1) & dp[순간이동] = min(dp[순간이동], dp[i]+1)와 같이 만들었다.

#include <iostream>
#include <vector>

using namespace std;

int N, K;

int minDist[1000001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N>>K;
    
    for(int i = 1; i<=1000000; i++){
        minDist[i]=987654321;
    }
    
    for(int i = 0; i<=999999; i++){
        minDist[i+1]=min(minDist[i+1], minDist[i]+1);
        
        int tel = i + i/2;
        
        if(tel<=1000000){
            minDist[tel] = min(minDist[tel], minDist[i]+1);
        }
    }
    
    if(minDist[N]>K){
        cout<<"water"<<endl;
    }else{
        cout<<"minigimbob"<<endl;
    }
    
    return 0;
}