A Plus Equals B

일단 문제가 영어러 되어있기 때문에 제가 이해한 문장을 적겠습니다.(원문을 보시고 싶다면, 위의 링크를 클릭해 문제를 풀고 오십숑)

A, B라는 두개의 자연수가 있다. 우리는 이 A, B 두 수를 같게 만들어야한다. 하지만 이 수를 같게 만드려면 아래의 4가지 방법 밖에 사용해야 한다.

1. A += A
2. A += B
3. B += A
4. B += B

이렇게 4가지의 과정을 잘 섞어서 두 수를 같게 만들어보자. 그런데 이 연산이 5000번은 넘으면 안된다.

답을 찾았다면, 연산 횟수를 먼저 출력하고 다음 줄부터 어떤 연산을 하였는지 차례대로 출력하여라!

내가 이해한 문제는 이렇다.

첨에는 음.. bfs로 다 찾는건가? 이러고 짜다가 alt+tab 이러고 읽고 풀고, 읽고 풀고 하다가 시간 초과가 의심되기 시작하면서, 머리가 띵해졌다…(일단 overflow문제도 뭔가 찜찜했었음..)

그러다가 A+=A, B+=B가 2배로 높아진다는 것을 알았다.

자 이제부터 어메이징한 것들이 나올 것이다.

A+=A 이것을 잘 생각해보면, B/=2와 같은 동작을 한다는 것을 알 수 있다.

왜?라고 생각할 수 있다. 자 생각해보자#

— 일단 나누는 수는 당연히 짝수라고 생각한다. —

어… 이 아이디어가 굉장히 어메이징한데…

어떤 수 A가 존재한다고 하자. A+=A를 진행하면 A는 2A가 된다. 다음 A가 같은 연산을 한다면 4A가 된다.

자 여기까진 이해가 쉽다.

이제 왜 A/=2가 B+=B와 같은 연산이라는건지 설명하겠다.

A=8, B=4 라고 생각해보자 이럴 때는 B*2 = A가 성립하면서, 굉장히 직관적으로 설명이 가능하다.

만약 A=100, B = 2 라고 생각한다면, 여러분들의 머릿속에는 ”??” 또는 “아하”가 나올 것이다.

먼저 결국 우리가 연산을 진행하면서 overflow를 막기 위해서 또한 좀 문제를 직관적으로 보기 위해서 계속해서 수를 좀 작게 만들고 있는데, A/2는 50인데 왜 2B하는 것과 같은 효과가 나오는 거야?라고 할텐데.

if문에서 보는 a, b는 홀수이다. (이건 명백하다)

그때 a+b를 한다면 무조건 짝수가 나온다.

A = 3, B = 9 이때, B+=A를 하게되면 B= 12가 된다. 이때 무조건 A가 2배를 해도 B보다 작다는 것은 알 수 있다. 그래서 A+=A해도 B와 작다. -> 그래서 반복 계속해서 이 과정을 반복하면 되는데, 이때 짝수가된 B를 계속해서 나눠주는 이유는 이와 같이 결국 A, B의 관계에서 “A+=A해도 B와 작다 -> 반복” 이것을 반복하면 점점 더 가까워지기 때문에 문제가 없을 것이라는 것을 알고 있기 때문이다.

5000번 이상의 연산이 없을 거란걸 생각하지 않고 제출하였는데, 넘어가는 것을 보니 그런 케이스는 딱히 없는 것같다. 이것 또한 기회가 된다면 찾아서 업데이트를 해놓도록 하겠다.(아마 안 할거 같긴해용)

#define MAX 2'100'000'000
#define limit 10'000'000'000
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <random>
using namespace std;

using ull = unsigned long long;
using ll = long long;

ull a, b;

int main() {
   
   
    cin >> a >> b;
    vector<string> result;
    
    
    while(a != b){
        
        while(a%2 == 0){
            a/=2; // == b+=b
            result.push_back("B+=B");
        }
        while(b%2 == 0){
            b/=2; // == a+=a
            result.push_back("A+=A");
        }
        
        // cout << 1;
        if(a > b){
            a+=b;
            result.push_back("A+=B");

        }
        else if(a < b){
            b+=a;
            result.push_back("B+=A");
        }
        
        
    }
    // cout << a << " " << b << "\n";
    
    cout << result.size() << "\n";
    for(string str : result){
        cout << str<<"\n";
    }
    
    
    return 0;
}