# 백준 : 숨바꼭질 (1697)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_1697_hideandseek)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

# define MAX 100000
int N, K;
int road[100001];

int main(void)
{
    cin>>N>>K;
    
    for(int i = 0; i <= K; i++) {
        if(i <= N) {
            road[i] = N - i;
            if((i > 0) && ((N - i) * 2) <= MAX) {
                road[(N - i) * 2] = (N - i) + 1;
            }
        }
        else
        {
            if(!road[i]) {
                road[i] = i - N;
            }
            if(i > 0) {
                road[i] = min(road[i], road[i - 1] + 1);
            }
            if((i % 2) == 0) {
                road[i] = min(road[i], road[i / 2] + 1);
            }
            if(((i + 1) <= MAX) && ((i + 1) % 2 == 0)) {
                road[i] = min(road[i], road[(i + 1)/2] + 2);
            }
        }
    }
    cout<<road[K]<<endl;
    return 0;
}

풀이

처음에는 백트래킹으로 문제를 풀어보았지만 시간초과가 발생하였다.
곧바로 DP로 접근 하였는데, 문제 조건 상 체크해야 할 부분들이 몇가지 있었다.

1. 시작 점 이하에서 부터 접근 하였을 때 최대치 값
2. 시작 점부터 접근 하였을 때 최대치 값
3. 이전 값 + 1
4. 짝수 값인 경우, x/2 + 1
5. 다음 값 + 1 (- 한번이므로)

근데 5번에서 체크해야 할 부분이 있다.

5.1. 다음 값이 x2로 만들어졌을 경우 + 2 (갔다가 되돌아오니까)

5.1을 생각하지 못해서 몇번 실패했지만 결국 성공했다!