[ 백준 17167 ] A Plus Equals B (c/c++)

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

 

 

[ 문제 요약 ]

두 양수 A, B가 주어졌을 때, "A+=A", "B+=B", "A+=B", "B+=A" 이 네가지 연산을 이용해서 두 수가 동일해지게 하는 연산의 최솟값과 그 연산 순서를 출력한다.

 

 

[ 문제 풀이 ]

1. 계속 더하는 연산은 숫자가 계속 커지기 때문에 오버플로우가 날 수 있다.

2. 따라서 "A+=A", "B+=B" 연산은 반대로 생각해서 "A/=2", "B/=2"로 연산하더도 문제가 없다.

3. A와 B가 만약 모두 홀수라면 큰 수에 작은 수를 더한다.

4. 두 수가 똑같아지면 종료한다. 

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

string A[4] = {"A+=A", "B+=B", "A+=B", "B+=A"};
vector<int> v;

int main() {
    long long a, b;
    cin >> a >> b;
    while (a!=b){
        if(b%2==0) {b/=2; v.push_back(0);}
        else if (a%2==0) {a/=2; v.push_back(1);}
        else if (a>b) {a+=b; v.push_back(2);}
        else {b+=a; v.push_back(3);}
    }
    cout << v.size() << "\n";
    for (int i=0; i<v.size(); i++) cout << A[v[i]] << "\n";
    return 0;
}

 

 

[ 주의할 점 ]

큰 수에서 작은 수를 더해야지 반복문이 종료되기 때문에 주의해야 한다.