[DP] 숨바꼭질 (1697)(C++)

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

1697번: 숨바꼭질

 

1. 문제 개요

 

수빈이가 점 N(0<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있을 때, 수빈이가 동생이 있는 위치로 가는 최소 시간을 구하는 문제. 이때, X 위치에서 X+1, X-1, 2*X 위치로 가는 데에는 각각 1초가 걸린다.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

우선, 수빈이가 동생보다 뒤에 있는 경우(N>K)와 수빈이가 동생보다 앞에 있는 경우(N<=K)로 나누어 볼 수 있다.

전자의 경우에는 -1로 이동하는 경우의 수 밖에 없으므로 정답은 N-K가 된다. 후자의 경우에는 다이나믹 프로그래밍으로 최소값을 구할 수 있다. 가능한 경우의 수는 +1, -1, *2 세 가지이므로 세가지 중에서 가장 작은 값을 선택하여 저장하면 된다.

 

이때, N에서 K로 가는 경우의 수를 구할때, N이하의 위치의 값이 쓰이는 경우도 있으므로 이도 구해준다. 

        for(int i=0;i<N;i++) { // N 이하의 값에 대해서 최솟값을 구해준다.
            DP[i] = N-i;
        }
        for(int i=N+1;i<=K+1;i++) {
            DP[i] = MAX;
            if(i%2==0)
                DP[i] = DP[i/2]+1;
            DP[i] = min(DP[i],DP[i-1]+1);
            DP[i-1] = min(DP[i-1],DP[i]+1);
        }

 

 

4. 전체 코드

 

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 100001;
int DP[MAX];

int main(void) {
    int N, K;
    scanf("%d%d",&N,&K);
    
    if(N>K) {
        printf("%d",N-K);
    } else {
        for(int i=0;i<N;i++) {
            DP[i] = N-i;
        }
        for(int i=N+1;i<=K+1;i++) {
            DP[i] = MAX;
            if(i%2==0)
                DP[i] = DP[i/2]+1;
            DP[i] = min(DP[i],DP[i-1]+1);
            DP[i-1] = min(DP[i-1],DP[i]+1);
        }
        printf("%d",DP[K]);
    }
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!