카프레카 수란 무엇일까요?
이 튜토리얼에서는 주어진 숫자가 카프레카 수(Kaprekar Number)인지 아닌지 판별하는 프로그램을 C++로 작성해 보겠습니다.
카프레카 수는 다음과 같은 특징을 가진 수입니다.
- 어떤 수를 제곱합니다.
- 제곱한 결과를 두 부분으로 나눕니다.
- 두 부분의 합이 원래 수와 같다면, 그 수를 카프레카 수라고 부릅니다.
예를 들어 45를 살펴보겠습니다. 45의 제곱은 2025이며, 이를 20과 25로 나누면 20 + 25 = 45로 원래 수와 일치합니다. 따라서 45는 카프레카 수입니다. 대표적인 카프레카 수로는 1, 9, 45, 55, 99, 297 등이 있습니다.
문제 해결 접근 방식
문제를 해결하기 위한 단계는 다음과 같습니다.
- 숫자 n을 초기화합니다.
- n의 제곱을 구합니다.
- n의 제곱값에 대한 자릿수를 계산하여 변수에 저장합니다.
- 자릿수 범위 안에서 제곱값을 10, 100, 1000 등으로 나누어 두 부분으로 분리합니다.
- 각 경우마다 두 부분의 합이 n과 같은지 확인합니다.
- 합이 n과 같으면 true를, 그렇지 않으면 false를 반환합니다.
C++ 구현 예제
위에서 설명한 알고리즘을 실제 코드로 작성해 보겠습니다.
#include<bits/stdc++.h>
using namespace std;
bool isKaprekarNumber(int n) {
if (n == 1) {
return true;
}
int nSquare = n * n, digitsCount = 0;
while (nSquare) {
digitsCount++;
nSquare /= 10;
}
nSquare = n * n;
for (int i = 1; i < digitsCount; i++) {
int parts = pow(10, i);
if (parts == n) {
continue;
}
int sum = nSquare / parts + nSquare % parts;
if (sum == n) {
return true;
}
}
return false;
}
int main() {
int n = 25;
string result = isKaprekarNumber(n) ? "True" : "False";
cout << result << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
False
25의 제곱은 625입니다. 이를 두 부분으로 나누어 더하면 6 + 25 = 31 또는 62 + 5 = 67이 되는데, 어느 경우에도 원래 수인 25와 일치하지 않습니다. 따라서 25는 카프레카 수가 아닙니다.
참고 사항
pow() 함수는 기본적으로 double 타입을 반환하기 때문에, 큰 수를 다룰 때는 부동소수점 오차가 발생할 수 있습니다. 정밀한 연산이 필요하다면 10의 거듭제곱 값을 직접 곱셈으로 계산하는 것이 더 안전합니다.
마무리
이번 튜토리얼에서는 C++를 활용하여 카프레카 수를 판별하는 알고리즘을 살펴보았습니다. 자릿수를 세고, 제곱값을 여러 지점에서 잘라 합을 비교하는 간단한 논리만으로 충분히 구현할 수 있다는 점이 인상적입니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요!