[BOJ][백준 16953] A -> B - C++

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

16953번: A → B

백준 사이트의 16953번 문제, A -> B 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

문제의 입력과 출력

• 백준 12919 문제인 A와 B 2 문제와 비슷한 문제라 풀어보았다.
• 12919 문제의 풀이는 다음으로

[BOJ][백준 12919] A와 B 2 - C++

---

1. 문제풀이 아이디어

• 아이디어가 같다. 결국 큰수에서 작은수로 수렴시키는 것이 포인트!
• 재귀의 방향을 어떻게 하느냐에 따라 코드의 성능이 천차만별로 변하는 경우이다. 
• 주어진 조건을 틀어서 더 효율적인 방식으로 생각해보는 문제.

---

2. 코드 핵심 부분

1) 문제 풀이의 전부인 재귀함수,

   N에서 M으로 가는 것이 아닌 M에서 N으로 가는 것을 확인할 수 있다.

   확실히 골드 난이도 문제인 12919 문제보다 숫자라 구현이 용이한 것을 볼 수 있다.

// 재귀적으로 M을 N으로 바꿔주는 함수
void solve(int N, int M, int lv) {
	// N과 M이 같아지면 찾은 것이다. 최소값 비교
    if (N == M) {
		if (lv < Min) {
			Min = lv;
			Ans = lv;
		}
		return;
	}

	// 만약 M이 N보다 작아지면 실패, return
	if (N > M) {
		return;
	}

	// 만약 짝수면 2로 나눠주며 체크
	if (M % 2 == 0) {
		solve(N, M / 2, lv + 1);
	}

	// 만약 1의자리가 1이면 이를 제거하며 체크
	if (M % 10 == 1) {
		solve(N, M / 10, lv + 1);
	}
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// 필요 인자들
int sN, sM;
int Min = 21e8;
int Ans = -1;

// 값 입력받는 함수
void input() {
	cin >> sN >> sM;
}

// 재귀적으로 M을 N으로 바꿔주는 함수
void solve(int N, int M, int lv) {
	// N과 M이 같아지면 찾은 것이다. 최소값 비교
    if (N == M) {
		if (lv < Min) {
			Min = lv;
			Ans = lv;
		}
		return;
	}

	// 만약 M이 N보다 작아지면 실패, return
	if (N > M) {
		return;
	}

	// 만약 짝수면 2로 나눠주며 체크
	if (M % 2 == 0) {
		solve(N, M / 2, lv + 1);
	}

	// 만약 1의자리가 1이면 이를 제거하며 체크
	if (M % 10 == 1) {
		solve(N, M / 10, lv + 1);
	}
}

void output() {
	cout << Ans;
}

// 메인함수
int main() {

	// input
	input();

	// solve
	solve(sN, sM, 1);

	// output
	output();

	return 0;
}

 

---

4. 문제 풀이를 마치며..

백준 채점 결과

사실 실버 문제는 잘 포스팅 안하지만,

우연히 이전에 포스팅한 문제와 이어지는 문제를 풀게되어 올리게 되었다.

 

제목을 안보고 푸는지라 아무생각 없이 문제를 딱 봤는데

왜인걸.

그때 내 발목을 약간 잡았던 문제를 숫자로 바꿔놓은것 뿐이었다.

 

점점 많고 다양한 문제들을 풀어서

실제 코딩테스트에서 이런 경험을 하게된다면 정말 좋겠다.