[백준 / 18004] From A to B - C++

 

www.acmicpc.net/problem/18004

18004번: From A to B

 

문제 : You are given two integers, a and b. You want to transform a into b by performing a sequence of operations. You can only perform the following operations:

• Divide a by two (but only if a is even)
• Add one to a

What is the minimum number of operations you need to transform a into b?

 

입력 : The single line of input contains two space-separated integers a and b (1 ≤ a, b ≤ 10^9)

 

출력 : Output a single integer, which is the minimum number of the given operations needed to transform a into b.

 

문제를 대충 해석하여 보면 1 이상 10^9이하의 정수 a,b를 입력받고

• a / 2 (a가 짝수일 때만)
• a + 1

a를 b로 바꾸기 위해 해야하는 가장 적은 연산의 갯수를 출력해야 한다.

 

입력받은 a가 b와 같다면  

• 연산을 안 하여도 a == b이므로 가장 적은 연산의 개수는 0번이다

입력받은 a가 b보다 작다면

• a == b가 될때까지 a + 1을 해준다. 따라서 가장 적은 연산의 개수는 b - a번이다.

입력받은 a가 b보다 크다면

• a가 만약 홀수라면 a + 1 해준다.
• a가 b보다 작아질때까지 a / 2 해준다. 
• 위 과정에서 a == b가 아니라면 a + 1 해준다. 반복문에서 이 과정을 수행한 뒤에 연산을 한 횟수를 카운트해준다.

정답 코드

#include <cstdio>
int main() {
    int a, b,i=0;
    scanf("%d %d", &a, &b);
    if (a == b) {
        printf("0");
    }
    else if (a < b) {
        printf("%d", b - a);
    }
    else {
        while (a>b) {
            if (a % 2 == 1) {
                a++;
            }
            else {
                a /= 2;
            }
            i++;
        }
        printf("%d",i+b-a);
    }
}