C++로 3자리 오시리스 수(Osiris Number) 판별하기

오시리스 수(Osiris Number)란?

오시리스 수는 자기 자신의 자릿수들로 만들 수 있는 모든 두 자리 순열의 합이 원래 수와 같아지는 특별한 수입니다. 이름은 이집트 신화에서 몸이 여러 조각으로 흩어졌다가 다시 하나로 조립된 신 오시리스에서 유래한 것으로 알려져 있습니다.

예를 들어 숫자 132를 살펴보겠습니다. 자릿수 1, 3, 2로 만들 수 있는 두 자리 순열은 12, 21, 13, 31, 23, 32이며, 이들을 모두 더하면 다음과 같습니다.
12 + 21 + 13 + 31 + 23 + 32 = 132
그 합이 원래 수인 132와 같으므로 132는 오시리스 수입니다. 대표적인 예로는 132와 264가 있습니다.

접근 방법

접근 방법은 아주 간단합니다. 세 자리 수의 경우, 가능한 모든 순열을 나열해 보면 각 자릿수는 일의 자리와 십의 자리 위치에서 정확히 두 번씩 등장합니다. 따라서 전체 순열의 합은 '각 자릿수의 합 × 22'와 같습니다. 결국 주어진 수 n이 자릿수 합의 22배와 같은지만 확인하면 됩니다.

알고리즘

isOsirisNumber(n) −

Begin
    a := 마지막 자릿수
    b := 가운데 자릿수
    c := 첫 번째 자릿수
    digit_sum := a + b + c
    if n = (22 * digit_sum), then
        return true
    end if
    return false
End

C++ 구현 예제

#include <iostream>
using namespace std;
bool isOsirisNumber(int n) {
    int a = n % 10;
    int b = (n / 10) % 10;
    int c = n / 100;
    int sum = a + b + c;
    if (n == (22 * sum)) {
        return true;
    }
    return false;
}
int main() {
    int n = 132;
    if (isOsirisNumber(n))
        cout << "오시리스 수입니다";
    else
        cout << "오시리스 수가 아닙니다";
}

실행 결과

오시리스 수입니다

동작 원리 정리

코드에서 a는 일의 자리, b는 십의 자리, c는 백의 자리 값을 추출합니다. 세 자릿수를 모두 더한 뒤 22를 곱해 입력값 n과 비교하는 방식으로, 별도의 반복문 없이 상수 시간 O(1) 안에 판별할 수 있어 매우 효율적입니다.