BOJ 1697 - 숨바꼭질

• 0<=N, K<=100000일 때 +1, -1, *2 세 가지 연산을 사용해서 N에서 K로 가는 최소 연산 횟수를 구하는 문제이다.

문제 풀이

• +1, -1, *2 세 가지 연산을 할 수 있는데 N에서 시작해서 이 세 연산들을 하면서 Dijkstra랑 비슷하게 연산 횟수를 값마다 저장하면서 BFS를 돌리면 된다.(N, K<=10^5이기 때문에 값을 인덱스로 사용 가능하다)

• 재귀로 바로 풀어버릴 수도 있다. 재귀함수는 아래와 같이 구현할 수 있다.(chungha님 코드 참고)

  int f(int n, int k){
    if(n>=k) return n-k;
    else if(k==1) return 1;
    else if(k&1) return 1+min(f(n, k-1), f(n, k+1));
    else return min(k-n, 1+f(n, k/2));
  }
  

증명

• 우선 +1, -1, *2연산을 통해 N에서 K로 가는 것과, -1, +1, /2연산을 통해 K에서 N으로 가는 것은 동일한 문제이다. 하지만 N->K는 {n-k}, {f(n+1, k), f(n-1, k), f(n*2, k)}로 케이스가 잘 나눠지지 않는데 비해 K->N은 {n-k}, {f(n, k-1), f(n, k+1)}, {k-n, f(n, k/2)}로 케이스가 잘 나눠져 비교적 재귀호출이 적다.
  (+ N->K를 재귀호출로 구현하면 DFS로 푸는 꼴인데 이 문제는 최소 연산 횟수를 구하는 것이기 때문에 BFS로 탐색하면서 N이 K가 되었을 때 탐색을 종료하면 시간이 훨씬 줄어든다. 근데 N->K 재귀로 구현해도 통과가 되긴한다.)

• N>=K일 때는 K-N 이외에 다른 연산을 할 수 없기 때문에 K-N을 반환한다.

• N<K일 때,

  • K==1이면 N=0, K=1인데, Edge case로 처리해준다.
  • K가 홀수면 +1, -1연산을 할 수 있다. 따라서 1+min(f(N, K-1), f(N, K+1))을 반환한다.
  • K가 짝수면 /2연산을 하거나 -1연산을 K-N번 해서 바로 N으로 갈 수 있다.(최적의 해인 최소 연산 횟수를 구하는 것이기 때문에 +1연산을 하는 경우 최적의 해가 아니게 된다. 즉 동전 dp문제에서 동전 가격이 1, 2, 4, 8과 같이 배수일 때와 비슷하게 그리디를 적용할 수 있다.)

따라서 위와 같이 재귀함수를 구현할 수 있다.
+1, -1, *3으로 나눌 경우 k%3!=0일 때 위/아래 3의 배수와 그 사이 K 이외의 수를 모두 포함해야 한다. (ex. K=4일 경우 3, 6, 5) 따라서 아래와 같이 재귀함수를 구현할 수 있다.

int f(int n, int k){
	if(n>=k) return n-k;
	else if(k==1) return 1;
	else if(k%3) return min(min(k%3+f(n, k-k%3), 3-k%3+f(n, k+3-k%3)), 1-2*(k&1)+f(n, k+1-2*(k&1)));
	else return min(k-n, 1+f(n, k/3));
}

소스코드

// // BFS
// #include<bits/stdc++.h>
// using namespace std;
// typedef pair<int, int> pii;

// int main()
// {
// 	int n, k, ccnt, cur, cnt;
// 	int v[100001];
// 	fill(v, v+100001, 100001);
// 	cin>>n>>k;
// 	ccnt=abs(k-n);
// 	queue<pii> q;
// 	q.push({n, 0});
// 	cur=n, cnt=0;
// 	while(cur!=k && cnt<ccnt){
// 		cur=q.front().first, cnt=q.front().second;
// 		q.pop();
// 		if(cur-1>-1 && v[cur-1]>cnt+1){
// 			q.push({cur-1, cnt+1});
// 			v[cur-1]=cnt+1;
// 		}
// 		if(cur+1<100001 && v[cur+1]>cnt+1){
// 			q.push({cur+1, cnt+1});
// 			v[cur+1]=cnt+1;
// 		}
// 		if(cur*2<100001 && v[cur*2]>cnt+1){
// 			q.push({cur*2, cnt+1});
// 			v[cur*2]=cnt+1;
// 		}
// 	}
// 	cout<<cnt;
// }

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

int f(int n, int k){	//K->N
	if(n>=k) return n-k;
	else if(k==1) return 1;
	else if(k&1) return 1+min(f(n, k-1), f(n, k+1));
	else return min(k-n, 1+f(n, k/2));
}

int g(int n, int k){	//N->K
	if(n>=k) return n-k;
	else if(n>0) return 1+min(f(n+1, k), min(f(n-1, k), f(n*2, k)));
	else return 1+min(f(n+1, k), f(n*2, k));
}

int main()
{
	int n, k;
	cin>>n>>k;
	cout<</*f(n, k)<<' '<<*/g(n, k);
}

풀고나서

• 문제 풀이 전략 중 거꾸로 생각해보기의 좋은 예시이다. 이 문제의 경우 N->K는 K 이상으로 더 갈수 있지만, K->N의 경우 K가 1로 수렴하기 때문에 N<K, K=1의 Edge case만 처리해주면 되기 때문에 재귀관계를 정의하기 더 편리하다. 근데 아무리 그래도 저렇게 깔끔하게 정리하는 것은 경험이 많이 필요한 것 같다.