[ 백준 16953 ] A → B (C++)

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

16953번: A → B

 

재귀함수로 쉽게 해결할 수 있는 문제다. 재귀함수가 정말 직관적이면서도 짜기 어려운 코드 같다. 그런데 꾸준한 연습으로 충분히 극복 가능한 영역이라고 생각한다. 예전에는 재귀함수 정말 어려워 했었는데 이 문제는 거의 10분 만에 푼 것 같다. 

 

딱히 설명할 게 많이 없다. 문제 조건대로 2를 곱해주거나 끝자리에 1을 더해 주는 것을 반복하면 된다. 종료 조건은 숫자가 일치하거나, 초과하거나 이렇게 두 가지다. Min 함수를 선언해줘서 최소값을 계속 갱신하면 된다. 코드를 보면 어렵지 않게 이해할 수 있을 것이다. 주의할 점은 자료형인데 A, B가 10억까지 허용돼서 끝자리에 1을 더해주는 경우 정수 자료형 범위를 초과하게 된다. 따라서 int가 아닌 long을 써줘야 한다.

 

#include <iostream>
#include <algorithm>
#define MAX 1000000000
using namespace std;

void dfs(long from, long to, int cnt, int* Min) {
	if (from == to) {
		*Min = min(*Min, cnt);
		return;
	}

	if (from > to)
		return;

	// dfs - 2를 곱하거나 뒤에 1을 붙이거나 둘 중 하나
	dfs(from * 2, to, cnt + 1, Min);
	dfs(from * 10 + 1, to, cnt + 1, Min);
}

int main() {

	long from, to;

	cin >> from >> to;

	int Min = MAX;
	dfs(from, to, 1, &Min);

	if (Min == MAX)
		cout << -1 << endl;
	else
		cout << Min << endl;

	return 0;
}