취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 18004번 문제인 From A to B이다.
문제는 아래 링크를 확인하자.

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

$a$가 홀수인 경우에는 $a$에 1을 더하는 것 외에는 아무런 연산을 할 수 없다. $a$가 짝수인 경우를 생각해보자.

$a$가 $b$보다 작다면 $a$를 $b$로 만드는 과정중에 $a$를 2로 나누는 연산을 할 필요가 없음은 쉽게 관찰할 수 있다. $a$의 값이 증가하는 방법은 유일하므로 $a$를 감소시키는 연산을 사용해 얻을 수 있는 이득이 없기 때문이다.

$a$가 $b$보다 크다면 $a$를 2로 나누는 연산을 바로 하는 것이 항상 이득이 된다. $a$의 값은 언젠가 감소해야하므로 $a$를 2로 나누는 연산을 언젠가 적용해야 하는데, 값을 $2k$회 증가시키고 2로 나누는 연산을 적용해 얻을 수 있는 값은 2로 나누는 연산을 먼저 한 뒤 값을 $k$회 증가시켜 항상 얻을 수 있기 때문이다.

위 규칙에 따라 $a$를 $b$로 바꾸는 과정 중 $a$가 $b$보다 클 때의 과정을 시뮬레이션 돌려보는 코드를 작성해 문제를 해결하자. 그 뒤 $a$의 값을 1씩 증가시키는 횟수는 두 수의 차로 단순하게 계산할 수 있음을 확인하자. 또한 $a$를 2로 나누는 횟수는 많아야 32회밖에 없다는 것 또한 관찰하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int A, B;
int cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B;
	while (A > B) {
		if (A & 1) A++;
		else A /= 2;
		cnt++;
	}
	cout << cnt + B - A;
}