C++에서 조건에 따라 반복적으로 변경될 때 X와 Y의 최종 값 구하기

두 양의 정수 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는 [0, 10¹⁸] 범위까지 가질 수 있으므로, 매번 2Y 또는 2X를 하나씩 빼는 단순 무식(brute force) 방식으로는 시간 제한 안에 해결할 수 없습니다. 대신 나머지 연산(%)을 활용하면 효율적으로 답을 구할 수 있습니다.

핵심 아이디어는 간단합니다. X에서 2Y를 여러 번 반복해서 빼는 것은 X mod 2Y를 구하는 것과 동일하기 때문입니다. 즉, "X ≥ 2Y" 조건을 만족하는 동안 계속 빼는 과정을 X = X % (2Y) 한 번의 연산으로 대체할 수 있으며, Y에 대해서도 마찬가지입니다.

예제 코드

#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) ≥ 2 × Y(10)이므로 X = 12 % 10 = 2

• Y(5) ≥ 2 × X(4)이므로 Y = 5 % 4 = 1

• X(2) ≥ 2 × Y(2)이므로 X = 2 % 2 = 0

• X = 0이 되었으므로 프로세스 종료 → 최종 결과는 X = 0, Y = 1

이처럼 나머지 연산을 사용하면 최악의 경우에도 반복 횟수가 로그 수준으로 줄어들어, 값이 10¹⁸만큼 커도 빠르게 최종 결과를 계산할 수 있습니다.