행운의 숫자(Lucky Number)란? 개념부터 판별 알고리즘까지

행운의 숫자(Lucky Number)란?

행운의 숫자는 특별한 성질을 가진 정수입니다. 자연수 목록에서 각 숫자의 값이 아닌 위치를 기준으로 일부 숫자를 단계적으로 제거하고, 최종적으로 삭제되지 않고 남은 숫자들이 바로 행운의 숫자가 됩니다.

삭제는 일정한 규칙에 따라 진행됩니다. 먼저 모든 2번째 숫자를 제거하고, 그다음에는 3번째 숫자를 제거합니다. 이후 단계에서는 살아남은 수열에서 다음 차례의 수에 해당하는 간격마다 숫자를 계속 제거해 나갑니다.

삭제 과정 예시

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 (1~25 전체)
1 3 5 7 9 11 13 15 17 19 21 23 25 (모든 2번째 숫자 삭제)
1 3 7 9 13 15 19 21 25 (5부터 시작해 모든 3번째 숫자 삭제)
1 3 7 9 13 15 21 25 (19부터 시작해 모든 7번째 숫자 삭제)

위 과정을 모두 거친 뒤 남은 1, 3, 7, 9, 13, 15, 21, 25가 행운의 숫자입니다.

입력과 출력

입력: 행운의 숫자인지 확인할 수를 입력합니다. 예를 들어 13을 입력한다고 가정해 보겠습니다.

출력: 13은 행운의 숫자입니다.

알고리즘

isLuckyNumber(number)

입력 − 검사할 숫자

출력 − 해당 숫자가 행운의 숫자인지 여부

Begin
    counter := 2 (정적 데이터이므로 재귀 호출 시 다시 초기화하지 않음)
    if counter > n, then
        return 1
    if n mod counter = 0, then
        return 0
    n := n – (n / counter)
    counter := counter + 1
    isLuckyNumber(n)
End

C++ 구현 예제

#include <iostream>
using namespace std;

int counter = 2;     //재귀 호출 시 사용되는 변수

bool isLuckyNumber(int n) {
    if(counter > n)
        return 1;
    if(n % counter == 0)
        return 0;

    n -= n / counter;     //n은 다음 재귀 호출에서의 위치 값
    counter++;
    return isLuckyNumber(n);
}

int main() {
    int x = 13;

    if(isLuckyNumber(x))
        cout << x << "은(는) 행운의 숫자입니다.";
    else
        cout << x << "은(는) 행운의 숫자가 아닙니다.";
}

실행 결과

13은(는) 행운의 숫자입니다.