백준 16953번 (C++)

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

16953번: A → B

1. 문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
2를 곱한다.
1을 수의 가장 오른쪽에 추가한다. 
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

2. 입력 / 출력

 가. 입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

 나. 출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

3. 알고리즘

• 거꾸로 생각하면 된다. B가 1로 끝나면 그 전 숫자는 B에서 1을 빼고 10으로 나눈 몫이고, B가 짝수이면 그 전 숫자는 B를 2로 나눈 몫이다.

 

4. 전체 코드

#include <stdio.h>

int main() {
	int A, B, count = 0;

	scanf_s("%d %d", &A, &B);

	while (B > A) {
		if (B % 2 == 0) {
			B = B / 2;
			count += 1;
		}
		else if (B % 10 == 1) {
			B = B / 10;
			count += 1;
		}
	}

	if (B == A) {
		printf("%d\n", count + 1);
	}
	else printf("%d\n", -1);
}

 

5. 코드 세부 설명

 가. 변수 선언

int main() {
	int A, B, count = 0;

• A : 정수 A (1 ≤ A < B ≤ 10^9)
• B : 정수 B (1 ≤ A < B ≤ 10^9)
• count : 계산 횟수

 나. 계산하는 부분

	scanf_s("%d %d", &A, &B);

	while (B > A) {
		if (B % 2 == 0) {
			B = B / 2;
			count += 1;
		}
		else if (B % 10 == 1) {
			B = B / 10;
			count += 1;
		}
	}

	if (B == A) {
		printf("%d\n", count + 1);
	}
	else printf("%d\n", -1);
}

 B가 A보다 클 동안만 계산을 하면 된다. 앞서 말했듯, B가 짝수이면 2로 나눈 몫을 구하면 되고 B가 1로 끝나면 10으로 나눈 몫을 구하면 된다.

 계산을 다 했을 때 B의 값이 A의 값과 같으면 count에 1을 더한 값을 출력하면 되고, A와 같지 않으면 -1을 출력하면 된다.