숫자 x가 주어졌을 때, 아래 세 가지 조건을 모두 만족하는 두 정수 a와 b를 찾아야 합니다.
- a와 b는 모두 1부터 x 사이의 값이어야 합니다.
- a는 b로 나누어 떨어져야 합니다.
- a × b > x를 만족하면서, 동시에 a ÷ b < x를 만족해야 합니다.
만약 이러한 두 수가 존재하지 않으면 -1을 출력합니다. 예를 들어 x = 10이 입력으로 주어지면, a = 10, b = 10이라는 답을 얻을 수 있습니다(물론 다른 조합도 가능합니다).
접근 방법
이 문제는 의외로 간단하게 해결할 수 있습니다. 핵심 아이디어는 a와 b를 모두 x로 설정하는 것입니다. x가 2 이상일 때 a = b = x로 두면 다음이 모두 성립합니다.
- 나누어떨어짐: x ÷ x = 1이므로 a는 항상 b로 나누어 떨어집니다.
- 곱셈 조건: a × b = x² > x는 x가 1보다 클 때 항상 참입니다.
- 나눗셈 조건: a ÷ b = 1 < x 역시 x가 1보다 클 때 항상 참입니다.
따라서 x ≥ 2인 경우 (x, x)가 항상 유효한 정답이 됩니다. 반면 x가 2보다 작은 경우(x = 1), 위 조건들을 동시에 만족하는 두 수를 찾을 수 없으므로 -1을 출력하면 됩니다.
구현 예시
#include <bits/stdc++.h>
using namespace std;
void solve(int x){
if (x < 2){
cout << -1;
return;
}
cout << x << ", " << x;
}
int main(){
int x = 10;
solve(x);
}
입력
10
출력
10, 10
복잡도 분석
이 알고리즘은 입력값에 대한 단순한 조건 검사 한 번만으로 해답을 결정하므로, 시간 복잡도는 O(1), 공간 복잡도 또한 O(1)입니다. 어떤 입력값이든 즉각적으로 결과를 계산할 수 있는 매우 효율적인 해법입니다.