C++로 수열 2, 4, 3, 4, 15…의 N번째 항 구하기

이 문제에서는 하나의 숫자 N이 주어지며, C++를 사용해 수열 2, 4, 3, 4, 15, 0, 14, 16 …의 N번째 항을 구하는 프로그램을 작성하는 것이 목표입니다.

문제 설명

주어진 수열에서 N번째 항의 값을 찾아야 하며, 이를 위해 수열의 일반항 공식을 먼저 유도해야 합니다.

예제로 문제 이해하기

입력 − N = 9

출력 − 9

풀이 접근 방법

수열의 값 증가는 선형적입니다. 즉, 수열에 제곱수가 포함되어 있지 않습니다. 또한 각 항의 값은 다른 요소에도 영향을 받는데, 특히 2와 3으로 나눈 나머지가 중요한 역할을 합니다(예: 6번째 항은 0이 됩니다).

먼저 수열의 각 항을 인덱스 N과의 관계로 분해해 살펴보겠습니다.

수열: 1×(2), 2×(2), 3×(1), 4×(1), 5×(3), 6×(0), …

이 패턴을 관찰하면 다음과 같은 일반항 공식을 도출할 수 있습니다.

T_n = N × ((N % 2) + (N % 3))

공식 검증

• N=1 → 1 × ((1%2)+(1%3)) = 1 × (1+1) = 2
• N=2 → 2 × ((2%2)+(2%3)) = 2 × (0+2) = 4
• N=3 → 3 × ((3%2)+(3%3)) = 3 × (1+0) = 3
• N=4 → 4 × ((4%2)+(4%3)) = 4 × (0+1) = 4
• N=5 → 5 × ((5%2)+(5%3)) = 5 × (1+2) = 15
• N=6 → 6 × ((6%2)+(6%3)) = 6 × (0+0) = 0

모든 항이 공식과 정확히 일치하므로, 이 공식을 그대로 코드로 옮기면 됩니다.

솔루션 구현 프로그램

#include <iostream>
using namespace std;
int findNTerm(int N) {
    int nthTerm = ( N*((N%2) + (N%3)) );
    return nthTerm;
}
int main()
{
    int N = 10;
    cout<<N<<"th term of the series is "<<findNTerm(N);
    return 0;
}

실행 결과:

10th term of the series is 10

N이 10일 때 10 × ((10%2)+(10%3)) = 10 × (0+1) = 10이므로, 프로그램은 정확히 10을 출력합니다.

이 풀이의 가장 큰 장점은 반복문 없이 모듈로(%) 연산만으로 N번째 항을 즉시 계산할 수 있다는 점입니다. 따라서 시간 복잡도는 O(1)로, N이 아무리 커져도 일정한 성능을 보장합니다.