[BOJ 18004 // C++] From A to B

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

 

이번에 볼 문제는 백준 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;
}