문제
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
c 로 작성된 코드 분석
BFS 를 통해 동생의 숫자값 노드까지 접근하면 return 하는 간단한 문제였다. 나는 이것을 파이썬으로 작성하였는데, c 언어로는 어떻게 풀어야될지 도저히 감이 오지 않았다. 그래서 다른 사람들이 인터넷에 올린 c 언어 코드를 분석하며 c 언어에 조금 익숙해지기로 하였다.
출처 : 백준-1697 c 언어 풀이
라이브러리 임포트
#include <stdio.h>
내 위치 = N, 동생 위치 = K
답을 구해주는 함수 c
int main(){
int N,K;
scanf("%d %d",&N,&K);
printf("%d",c(K,N));
}
두 값 중 더 작은 값을 찾아주는 min
int min(int a,int b){
return a<b? a:b;
}
함수 c 내부 1
int c(int p,int d){
if (p<=d)
return d-p;
}
내가 순간이동하는 옵션은 -1 , +1 , *2 이다. 이 중 내 위치가 더 작아지는 옵션은 -1 밖에 없다. 따라서 동생의 위치가 나보다 작은 숫자값에 있다면 계속 1초마다 -1 하면서 동생의 위치까지 돌아가야 한다.
함수 c 내부 2
else if (p==1)
return 1;
반면 내가 0 이고 동생은 1이라면 바로 +1 해서 동생이 있는 위치로 가면 되므로 1초가 걸린다.
함수 c 내부 3
동생의 위치가 내 위치보다 클 때 (=동생이 나보다 더 멀리 가 있는 상황) 내가 제일 빠르게 동생의 위치 언저리까지 가는 법은 *2 옵션을 선택하는 것이다. 하지만 동생의 위치가 2로 나누어떨어지지 않는다면 내 현재 위치가 어디든지 2배 증가해서 어차피 동생의 위치까지 갈 수 없다. 따라서 동생의 위치 최대한 언저리까지 내 위치에서 2배하여 도착한 후 / -1 혹은 +1 을 해주는게 베스트일 것이다.
ex. 내 위치 : 5 , 동생의 위치 : 17
5 ❓❓❓(어떠한 순간 이동) 16 도착 ! ➕ 1 = 17
혹은
5 ❓❓❓(어떠한 순간 이동) 18 도착 ! ➖ 1 = 17
else if (p%2)
return 1+min(c(p-1,d),c(p+1,d)));
함수 c 내부 4
동생의 위치가 내 위치보다 클 때 (=동생이 나보다 더 멀리 가 있는 상황) 내가 제일 빠르게 동생의 위치 언저리까지 가는 법은 *2 옵션을 선택하는 것이다. 이 때 동생의 위치가 2로 나누어떨어진다면 내 현재 위치가 동생의 위치의 절반 지점이라면 딱 1초만에 2배 멀리 가서 동생의 위치까지 한 번에 도착할 수가 있다. 혹은 1초에 1씩 거리를 증가시켜가며 동생의 위치에 도착할 수도 있다.
ex. 내 위치 : 5, 동생의 위치 : 6
5 ➕ 1 = 6
5 ➖ 1 ➖ 1 =3 ✖️2 = 6 (3은 동생의 위치 딱 중간 지점 ! )
이 경우는 그냥 1 증가하는 것이 빠르다.
else
return min(p-d,1+c(p/2,d)));
이 코드를 작성한 사람은 디게 똑똑한 분인 것 같다. 열심히 살아야 겠 다 ….