C++에서 주어진 조건을 만족하는 두 수 a와 b 찾기

정수 n이 하나 주어졌다고 가정해 봅시다. 우리의 과제는 다음 세 가지 조건을 모두 만족하는 두 수 a와 b를 찾는 것입니다.

• a mod b = 0
• a * b > n
• a / b < n

조건을 만족하는 쌍이 존재하지 않으면 -1을 출력하면 됩니다.
예를 들어 n = 10인 경우, a = 90, b = 10으로 선택하면 세 조건을 모두 만족합니다.

• 90 mod 10 = 0 ✔
• 90 × 10 = 900 > 10 ✔
• 90 ÷ 10 = 9 < 10 ✔

문제 해결 접근법

이 문제는 복잡한 탐색 없이 간단한 수학적 관찰만으로 해결할 수 있습니다. 핵심은 b의 값을 먼저 고정하는 것입니다.

• 1단계: b = n으로 설정합니다. 이후 나머지 조건들을 이용해 a를 유도할 수 있습니다.
• 2단계: a mod b = 0 조건을 만족하려면 a가 반드시 b의 배수여야 합니다.
• 3단계: a / b < n 조건을 만족시키기 위해 몫을 n - 1로 만듭니다. 즉, a / b = n - 1 (< n)이 됩니다.
• 4단계: 위 식을 정리하면 a = b × (n - 1)이고, 이때 a × b = n² × (n - 1)이므로 n ≥ 2인 경우 항상 a × b > n 조건도 자동으로 충족됩니다.

따라서 최종 공식은 b = n, a = n × (n - 1)입니다.

예제 코드

#include<iostream>
using namespace std;

void findAandB(int n) {
   int b = n;
   int a = b * (n - 1);
   if (a * b > n && a / b < n) {
      cout << "a: " << a << endl;
      cout << "b: " << b;
   } else {
      cout << -1 << endl;
   }
}

int main() {
   int n = 10;
   findAandB(n);
}

출력 결과

a: 90
b: 10

n = 10일 때 a = 10 × 9 = 90, b = 10이 계산되며, 앞서 확인한 대로 세 조건을 모두 만족합니다. 이 풀이는 반복문 없이 상수 시간(O(1))에 답을 구할 수 있다는 장점이 있습니다. 다만 n이 매우 클 경우 곱셈 과정에서 정수 오버플로가 발생할 수 있으므로, 필요하다면 long long 타입 사용을 고려하는 것이 좋습니다.