백준 16953번 A → B C++

리뷰

BFS도 가능하지만 그리디 알고리즘으로 풀이가 가능하다.

 

문제 풀이

1. b에서 a로 가는 방법으로 풀이한다.
2. while루프의 조건은 a가 b보다 작거나 같을때 실행, cnt를 1 상승시키고 만약 a와 b가 같다면 루프를 종료한다.
3. 현재 b의 뒷자리가 1이라면 b를 10으로 나눈 몫을 b로 갱신해 준다.
4. 만약 b가 짝수라면 b를 2로 나눈 몫을 b로 갱신해 준다.
5. 둘다 해당되지 않다면 -1을 출력하고 리턴한다.
6. 중간에 리턴되지 않고 루프가 종료되었을때 a가 b보다 크다면 -1을, 아니라면 cnt를 출력한다.

 

참고 사항

while루프가 종료되는 경우는 다음과 같다.

1. 1의 자리 뒤에 1을 붙이거나 2를 곱해도 a가 결코 b가 될 수 없을 때
2. a가 b보다 커져서 루프가 종료 되었을 때

 

정답 코드

#include <iostream>

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	int cnt = 0;
	while (a <= b) {
		cnt++;
		if (a == b) break;
		if (b % 10 == 1) {
			b /= 10;
			continue;
		}
		else if (b % 2 == 0) {
			b /= 2;
		}
		else {
			cout << -1;
			return 0;
		}
	}
	if (a > b) cout << -1;
	else cout << cnt;
}