C++로 2/n = 1/x + 1/y + 1/z를 만족하는 x, y, z 구하기

문제 개요

이 문제에서는 정수 n이 하나 주어지며, 우리의 목표는 2/n = 1/x + 1/y + 1/z 등식을 만족하는 세 정수 x, y, z를 찾는 것입니다.

예시를 통해 문제를 살펴보겠습니다.

입력 : n = 4
출력 : 4, 5, 20

출력된 값이 실제로 등식을 만족하는지 확인해 보면 다음과 같습니다.
1/4 + 1/5 + 1/20 = 5/20 + 4/20 + 1/20 = 10/20 = 2/4 = 2/n ✔

풀이 접근 방법

이 문제는 n의 값만으로 해를 바로 유도할 수 있는 아주 단순한 수학적 구조를 가지고 있습니다.

• n = 1인 경우: 등식을 만족하는 해가 존재하지 않습니다.
• n > 1인 경우: 항상 해가 존재하며, 그 해는 x = n, y = n+1, z = n(n+1) 입니다.

이 해가 성립하는 이유를 수식으로 증명하면 다음과 같습니다.

2/n = 1/n + 1/(n+1) + 1/(n(n+1))
= (n+1)/[n(n+1)] + n/[n(n+1)] + 1/[n(n+1)]
= (2n + 2)/[n(n+1)]
= 2(n+1)/[n(n+1)]
= 2/n

즉, 분모를 통분했을 때 분자가 정확히 2(n+1)이 되어 우변이 2/n과 일치함을 알 수 있습니다.

예제 코드

아래 C++ 프로그램은 위에서 설명한 풀이 로직이 실제로 작동하는 모습을 보여줍니다.

#include <iostream>
using namespace std;

void findSolution(int n){
   // n이 1이면 해가 존재하지 않음
   if (n == 1) {
      cout << "해가 존재하지 않습니다";
      return;
   }
   // x = n, y = n+1, z = n*(n+1)
   cout << n << ", " << (n + 1) << ", " << (n * (n + 1));
}

int main(){
   int n = 4;
   cout << "n = " << n << "일 때, 방정식 '2/n = 1/x + 1/y + 1/z'의 해는 ";
   findSolution(n);
   return 0;
}

출력 결과

n = 4일 때, 방정식 '2/n = 1/x + 1/y + 1/z'의 해는 4, 5, 20

복잡도 및 마무리

이 풀이 방법은 반복문 없이 n 값에 대한 산술 연산 한 번으로 해를 계산하므로, 시간 복잡도는 O(1)입니다. 어떤 큰 n 값이 입력되더라도 즉시 해를 구할 수 있다는 점에서 매우 효율적입니다.

정리하면, n > 1인 모든 정수에 대해 (n, n+1, n(n+1))이라는 해가 항상 존재하며, n = 1일 때만 해가 없다는 사실만 기억하면 이 문제는 코드 몇 줄로 해결됩니다.