숨바꼭질 | 백준 1697번

#include <iostream>
using namespace std;

int main() {
 int n, k;
 int pos[100001];
 
 cin >> n >> k;
 
 for(int i=0; i<=n; i++) pos[i] = n-i;
 
 for(int i=n+1; i<=k; i++)
 {
  int min;
  
  if(i%2==0) min = pos[i/2]+1;
  else min = pos[i/2]+2 < pos[(i+1)/2]+2 ? pos[i/2]+2 : pos[(i+1)/2]+2;
   
  pos[i] = min < pos[i-1]+1 ? min : pos[i-1]+1;
 }
 
 cout << pos[k];
 
 return 0;
}

이것 참.. 분명 DP가 아닌데, DP로 풀어내는 기분이지만.. 그렇다. 알고리즘 간단하다.

동생의 위치가 더 작은 경우

• 수빈이와의 거리만큼의 값을 갖는다.

동생의 위치가 더 큰 경우

1. 짝수일 경우는 절반인 위치보다 1큰 값을 받음 (왜냐면 절반에서 한번 움직인거니까). 
2. 홀수인 경우는 절반인 위치가 n + 1/2 이고, 따라서 n, n+1 중 작은 것을 택해서 2 큰 값을 받는다.
   예를 들면, 11인 경우, 5.5가 절반이기 때문에, 5나 6을 택하고, 이것의 두배 한 값에서 하날 올리거나 내리므로, 두번의 움직임이 필요 (2배하는데 한번, 움직이는데 한번).
3. 1, 2의 경우 모두 직전 값에서 1큰 값과 비교하여 더 작은 것을 선택. 왜냐면, 직전거에서 한번 움직여서 올 수 있으니까.

알고리즘 분류 : bfs, dfs, 백트래킹

• Twitter
• Facebook
• Google
• Tumblr
• Pinterest