[백준 / C언어] 16953번: A → B

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

16953번: A → B

 

난이도: solved.ac 실버 2

 

 

BFS 문제라고 하는데, BFS로 풀면 괜히 복잡해져서 머리 아플 것 같다

 

나는 재귀로 풀었다 (근데 다른 분들이 푼 방식이 더 나은듯.. 아래 참고)

 

found라는 변수의 초기값은 0인데 A = B가 되면 1로 바꿔주고, main 함수 내에서 found = 0 이면 -1을, found = 1이면 연산 횟수를 출력하도록 해주었다

 

연산 횟수는 cnt라는 변수를 이용했는데 A*2를 하거나 A*10+1을 할 때마다 cnt를 1씩 늘려주었고

 

재귀 함수 호출을 하다가 A > B가 되면 다시 return을 해주면서 cnt를 1 감소시켜주었다

 

그리고 A와 B의 범위는 10^9까지인데, int형의 범위가 약 2*10^9라서

 

A*2와 A*10+1 값이 10^9를 넘지 않도록 해주었다

 

(내 코드)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int A, B;
int cnt = 0;
int found = 0;
int find(int A);

int main() {
	scanf("%d %d", &A, &B);
	find(A);
	if (!found)
		printf("-1");
	return 0;
}

int find(int A) {
	cnt++;
	if (A == B) {
		found = 1;
		printf("%d", cnt);
		return;
	}
	else if (A > B || A >= 500000000)
		return;
	else {
		find(A * 2);
		cnt--;
		if (A >= 100000000)
			return;
		find(A * 10 + 1);
		cnt--;
	}
}

 

나는 A를 B로 만들려고 노력했지만, 다른 분들의 깔끔한 코드에서는 B를 A로 만들려고 했다

 

while문 내에서 끝내버리고 코드의 가독성도 좋아 내가 작성한 코드보다 훨씬 좋은 것 같다..

 

(깔끔한 코드)

#include<stdio.h>
int a, b;

int main() {
	scanf("%d %d", a, b);
	int cnt = 0;
	while (1) {
		if (a > b) {
			printf("-1");
			break;
		}
		if (a == b) {
			printf("%d", cnt + 1);
			break;
		}

		if (b % 10 == 1) {
			b /= 10;
		}
		else if (b % 2 == 0) {
			b /= 2;
		}
		else {
			printf("-1");
			break;
		}
		cnt++;
	}
	return 0;
}