문제 설명
두 숫자 l과 r가 주어졌을 때, 다음 조건을 모두 만족하는 쌍 (x, y)를 찾는 것이 목표입니다.
- l ≤ x, y ≤ r (두 수 모두 구간 안에 있어야 함)
- x ≠ y (두 수는 서로 달라야 함)
- x는 y를 나누어 떨어지게 함 (즉, y는 x의 배수)
조건을 만족하는 답이 여러 개라면 그중 아무거나 하나만 출력하면 됩니다.
예를 들어 l = 3, r = 14가 입력으로 주어지면, (3, 6) 또는 (3, 9)처럼 3의 배수를 포함하는 쌍을 출력할 수 있습니다.
접근 방법
이 문제의 핵심 아이디어는 매우 간단합니다. 구간 [l, r] 안에서 배수 관계가 성립하려면, 구간의 최솟값인 l의 두 배인 2 × l도 반드시 구간에 포함되어야 합니다(정답이 존재한다는 전제하에).
따라서 정답이 존재하는 경우에는 항상 (l, 2 × l)이 유효한 답이 됩니다. l은 구간의 최솟값이므로 범위 조건을 만족하고, 2 × l은 l보다 크면서 l로 정확히 나누어 떨어지기 때문입니다.
알고리즘 단계
- l과 2 × l을 차례대로 출력합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
void solve(int l, int r){
cout << l << ", " << l * 2;
}
int main(){
int l = 3;
int r = 14;
solve(l, r);
}입력
3, 14
출력
3, 6
복잡도 분석
시간 복잡도: O(1) — 단순히 두 값을 출력하면 되므로 상수 시간에 해결됩니다.
공간 복잡도: O(1) — 추가적인 메모리가 필요하지 않습니다.
주의 사항
이 풀이는 2 × l ≤ r인 경우, 즉 구간 내에 배수 관계를 이루는 쌍이 실제로 존재할 때 유효합니다. 만약 2 × l > r이라면 구간 [l, r] 안에서는 조건을 만족하는 쌍이 존재하지 않습니다. x ≥ l인 임의의 수 x에 대해 x ≠ y이면서 x가 y를 나누는 가장 작은 y는 2x ≥ 2l이기 때문입니다.