나의 소울메이트는 어디에? (Searching for Soulmates) (JUNGOL 5341)

https://jungol.co.kr/problem/5341?cursor=MTMsMSwx

---

아이디어

a에서 연산을 할 때에 곱셈을 한번 하고 그 다음에 나눗셈을 하는 경우는 없습니다.

증명) 만약 그러한 경우가 존재한다고 해봅시다. 그리고 덧셈 연산을 빼고 곱셈과 나눗셈 연산만 남겨봅시다. 그러면 곱셈 바로 다음에 나눗셈이 등장하는 경우가 적어도 한 번 나타나게 됩니다. 이러한 경우 덧셈까지 고려하면 (곱셈) -> (덧셈) k번 -> (나눗셈)의 형태가 됩니다. 이떄 곱셈을 한 후에 수가 짝수이고 나눗셈을 하기 전에 수가 짝수이므로 k 또한 짝수가 됩니다. 그러면 위 k+2개의 연산을 사실 k/2개의 덧셈으로 표현할 수 있습니다. 그러므로 저러한 경우는 존재하지 않습니다.

 

그러면 항상 나눗셈이 몇번 등장하고 곱셈이 몇번 등장하게됩니다. 그러므로 a를 나눗셈과 덧셈만으로 최대한 작게 만들면서, 그 과정에서 생기는 a'들을 저장하고, b에서 a'으로 가는 역연산의 최소 횟수도 저장하여 a->b로 가는 최소 횟수를 구해주면 됩니다.

---

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll change(ll a,ll b) //a를 2로 나누는것과 1을 빼는것을 반복하여 b를 만들기
{
    ll cnt=0;

    while (a!=b)
    {
        if (a%2==0)
        {
            if (a/2>=b) a/=2;
            else
            {
                cnt+=a-b;
                break;
            }
        }
        else a--;
        cnt++;
    }
    
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T,a,b;

    cin>>T;
    while (T--)
    {
        cin>>a>>b;

        ll res=1e18,cnt=0;
        while (true)
        {
            if (a<=b) res=min(res,cnt+change(b,a));

            if (a==1) break;
            if (a%2==0) a/=2;
            else a++;
            cnt++;
        }

        cout<<res<<"\n";
    }
}