C++로 특정 범위에서 x가 y를 나누는 고유한 쌍 (x, y) 찾기

문제 소개

이번 글에서는 흥미로운 알고리즘 문제를 다뤄보겠습니다. 주어진 범위 내에서 한 쌍 (x, y)를 찾아야 하며, 조건은 l ≤ x, y ≤ r입니다. 이 쌍은 x가 y를 나눈다(x divides y)는 특성을 가져야 합니다. 만약 조건을 만족하는 쌍이 여러 개 존재한다면, 그중 하나만 골라 출력하면 됩니다.

접근 방법

이 문제는 O(1) 시간 복잡도로 해결할 수 있습니다. 핵심 아이디어는 하한값 l과 그 두 배 값인 2l을 활용하는 것입니다.

y/x 비율의 최솟값은 2입니다. 만약 범위 안에 더 큰 배수 관계가 존재한다면, 반드시 2배 관계 역시 범위 안에 포함됩니다. 또한 x가 커질수록 2x도 함께 커지기 때문에, 주어진 범위에 속하는 가장 작은(그리고 항상 유효한) 쌍은 (l, 2l)이 됩니다.

따라서 2l ≤ r이라면 정답은 (l, 2l)이고, 그렇지 않다면 조건을 만족하는 쌍이 존재하지 않습니다. 아래 코드에는 이 유효성 검사까지 추가하여 완성도를 높였습니다.

예제 코드

#include<iostream>
using namespace std;

void getPair(int l, int r) {
    if (2 * l <= r) {
        cout << "(" << l << ", " << 2 * l << ")" << endl;
    } else {
        cout << "조건을 만족하는 쌍이 존재하지 않습니다." << endl;
    }
}

int main() {
    int l = 3, r = 6;
    getPair(l, r);
    return 0;
}

출력 결과

(3, 6)

위 예제에서 l = 3, r = 6이므로 2 × 3 = 6이 r 이하입니다. 따라서 (3, 6)이 정답으로 출력되며, 실제로 3은 6을 나눕니다. 이처럼 단순한 수학적 관찰만으로 상수 시간 안에 문제를 해결할 수 있습니다.