C++로 n번째 별 수(Star Number)를 구하는 프로그램

이 문제에서는 숫자 n이 주어지며, 우리의 과제는 C++로 n번째 별 수(Star Number)를 찾는 프로그램을 작성하는 것입니다.

별 수(Star Number)는 중심 육각별(centered hexagram), 즉 육각 별 모양으로 배열된 점들의 개수를 나타내는 특수한 수입니다.

별 수의 예시로는 1, 13, 37, 73, 121 등이 있습니다.

문제 이해를 위한 예시

입력

n = 5

출력

121

해결 방법

n번째 별 수를 구하기 위해 일반화된 공식을 사용할 수 있습니다. 먼저 몇 가지 항을 살펴보며 규칙을 찾아보겠습니다.

n = 2 -> 13 = 12 + 1 = 6×2 + 1
n = 3 -> 37 = 36 + 1 = 6×6 + 1
n = 4 -> 73 = 72 + 1 = 6×12 + 1
n = 5 -> 121 = 120 + 1 = 6×20 + 1

위 항들을 분석하면 각 항은 6 × (n × (n-1)) + 1 형태를 따른다는 것을 알 수 있습니다. 여기서 곱해지는 값 2, 6, 12, 20은 사실 삼각수의 두 배인데, 이는 육각별 모양이 두 개의 삼각형이 겹쳐진 구조이기 때문입니다.

따라서 n번째 항의 일반 공식은 다음과 같습니다.

N번째 항 = 6 × (n × (n-1)) + 1

공식을 검증해 보면,

n = 5일 때, 6 × (5 × 4) + 1 = 120 + 1 = 121 ✓

구현 예제

다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;

int findStarNo(int n){
    int starNo = ( 6*(n*(n - 1)) + 1 );
    return starNo;
}

int main(){
    int n = 4;
    cout<<"The star number is "<<findStarNo(n);
    return 0;
}

출력 결과

The star number is 73

이 프로그램은 findStarNo 함수에서 공식을 적용하여 계산한 뒤 결과를 반환합니다. 시간 복잡도는 O(1)로, 어떤 n값이 주어져도 상수 시간 안에 별 수를 계산할 수 있다는 장점이 있습니다.