BOJ (C/C++) 16953번: A → B

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

16953번: A → B

---

풀이

2를 곱하는 경우와 뒷자리에 1을 붙이는 경우 각각 B보다 작을 경우에 재귀를 돌렸고, B가 됐을 때 cnt 값을 구하여 min 갱신.

이게 왜 BFS인지 모르겠어서 다른 분들 코드를 찾아보니 재귀 대신 큐를 사용하는 코드가 보였다. 확실히 이 방법으로 푼다면 -1을 출력하는 경우를 만들기 더 쉬웠을 것 같다. 

---

코드

#include <stdio.h>
int min = 0;
void Cal(long int now, int end, int cnt) {
	if (now == end) {
		if (!min) min = cnt;
		else if (cnt < min) min = cnt;
		return;
	}
    
	if (now * 2 <= end) Cal(now * 2, end, cnt + 1);
	if (now * 10 + 1 <= end) Cal(now * 10 + 1, end, cnt + 1);

	// 만들 수 없는 경우
	if (cnt == 1 && !min) min = -1;
}

int main() {
	int A, B;
    
	scanf("%d %d", &A, &B);
    
	Cal(A, B, 1);
	printf("%d", min);
    
	return 0;
}