두 양의 정수 X와 Y의 초기값이 주어져 있다고 가정해 보겠습니다. 이때 아래 규칙에 따라 값이 반복적으로 변경된 이후의 최종 X와 Y 값을 구하는 것이 이 글의 목표입니다.
문제의 규칙
- 1단계 – X = 0 또는 Y = 0이면 프로세스를 즉시 종료하고, 그렇지 않으면 2단계로 이동합니다.
- 2단계 – X ≥ 2Y이면 X = X − 2Y로 갱신한 뒤 1단계로 돌아가고, 그렇지 않으면 3단계로 이동합니다.
- 3단계 – Y ≥ 2X이면 Y = Y − 2X로 갱신한 뒤 1단계로 돌아가고, 그렇지 않으면 프로세스를 종료합니다.
X와 Y는 최대 1018까지 입력될 수 있기 때문에, 단순히 2Y씩 반복해서 빼는 무식한(Brute Force) 방식은 시간 제한 안에 동작하지 못할 수 있습니다. 대신 모듈로(나머지) 연산을 활용하면 반복 횟수를 한 번의 연산으로 줄여 매우 큰 입력값도 빠르게 처리할 수 있습니다.
왜 나머지 연산이 가능한가?
X ≥ 2Y인 상황에서 X에서 2Y를 계속 빼는 행위는 결국 X mod 2Y를 구하는 것과 수학적으로 동일합니다. 예를 들어 X = 12, Y = 5일 때 X에서 2Y(=10)를 한 번 빼면 2가 되는데, 이는 12 % 10 = 2와 같습니다. 마찬가지로 Y ≥ 2X인 경우에는 Y mod 2X를 한 번만 계산하면 됩니다. 덕분에 알고리즘의 전체 시간 복잡도는 유클리드 호제법과 유사하게 로그 수준으로 줄어듭니다.
C++ 예제 코드
#include<iostream>
using namespace std;
void alterNumber(long long x, long long y) {
while (1) {
if (x == 0 || y == 0)
break;
if (x >= 2 * y)
x = x % (2 * y);
else if (y >= 2 * x)
y = y % (2 * x);
else
break;
}
cout << "X: " << x << "\n" << "Y: " << y;
}
int main() {
long long x = 12, y = 5;
alterNumber(x, y);
}실행 결과
X: 0 Y: 1
코드 동작 과정 살펴보기
입력값이 x = 12, y = 5인 경우를 단계별로 추적해 보면 다음과 같습니다.
- x = 12, y = 5 → x ≥ 2×5(=10)이므로 x = 12 % 10 = 2
- x = 2, y = 5 → y ≥ 2×2(=4)이므로 y = 5 % 4 = 1
- x = 2, y = 1 → x ≥ 2×1(=2)이므로 x = 2 % 2 = 0
- x = 0이 되었으므로 반복문을 탈출하고 최종 결과 X: 0, Y: 1을 출력합니다.
이처럼 나머지 연산을 사용하면 값이 클 경우에도 몇 번의 연산 만으로 최종 결과에 도달할 수 있어, 실전 코딩 테스트나 경쟁 프로그래밍에서 유용하게 활용할 수 있는 패턴입니다.