BOJ 17167 : A Plus Equals B

문제 링크 : https://www.acmicpc.net/problem/17167

 

편법으로 파이썬을 쓴 문제...

long long 범위의 두 자연수 A, B 가 주어졌을 때

A += A,   A += B,   B += A,   B += B 의 네 연산을 적절히 써서 A == B 가 되게 만들라는 문제다.

이 때, 주의할 점은 꼭 최소 횟수일 필요가 없다는 것이다. A와 B가 같게만 되면 된다.

 

일반성을 잃지 않고, 마지막에 A 가 커져서 B와 같아졌다고 해보자.

그렇다면, A += A 가 무조건 마지막 연산이 되어야 한다. A += B 를 했는데 B 와 같아질 수 없기 때문.

여기서 조금만 더 나아가면, 마지막은 A += A 가 1번 이상 반복된 형태여야 함을 쉽게 알 수 있다. 

즉 A 가 1번 이상 2배가 된다는 것이다.

 

그렇다면,  B 입장에서는 마지막 연산이 어떤 것이어야 할까?

B += B 는 불필요하다. 어차피 마지막에 A 가 1번 이상 2배가 되어서 B와 같아져야 하기 때문이다.

즉, B += A 가 B 입장에서는 마지막 연산이 되어야 한다.

 

여기까지의 내용을 정리하면,

A 입장에서 마지막은 A += A 를 1번 이상 반복한 형태고,

B 입장에서 마지막은 B += A 를 한 형태라는 것이다.

그렇기 때문에, B += A 를 한 직후에는 B = A * 2^k 꼴이 되어야만 한다.

 

A = 2^a * x  ,   B = 2^b * y   ( x,  y 는 홀수 ) 일때, (B + A) 가 A * 2^k 꼴이 될 필요조건을 생각해보자.

1 ) a > b 라면 A + B = 2^b (2^a-b * x + y) 이다. a > b 인데다가,  a - b > 0 이기 때문에 괄호 안은 홀수가 된다. 불가능.

2 ) a < b 라면 A + B = 2^a (2^b-a * x + y) 이다. 마찬가지로 b - a > 0 이기 때문에 괄호 안은 홀수가 되어 불가능.

따라서, a == b 가 일단 되어야 함을 알 수 있다.

역은 성립하지 않는다. 즉, a == b 가 된다고 해서 무조건 (B + A) 가 A * 2^k 꼴이 되지는 않는다.

 

이제 최종 알고리즘이 나왔다.

A, B의 2의 지수가 다르다면? 한쪽이 다른쪽과 같아질 때까지 2배를 계속 해준다. (A+=A  or B+=B)

2의 지수가 같아졌다면? 더 큰 쪽에 더 작은 수를 더해준다. (ex : A > B 라면 A += B)

이를 A == B 가 될 때까지 반복해주면 된다.

 

파이썬이기 때문에 가능했던 풀이

C++ 로 하려면 A, B를 직접 키우는게 아니라 | A - B | 를 줄이는 발상으로 가야할 것이다.