C++로 수열 1 2 2 3 3 3 4…의 n번째 항 구하는 프로그램

문제 개요

이 문제에서는 정수 N이 하나 주어지며, 수열 1 2 2 3 3 3 4…에서 n번째 항을 찾는 것이 목표입니다. 이 수열은 숫자 1이 한 번, 2가 두 번, 3이 세 번씩 반복되어 나타나는 특징적인 패턴을 가집니다.

예제로 문제 이해하기

입력:

N = 6

출력:

3

설명: n번째 항까지의 수열은 1, 2, 2, 3, 3, 3, ... 입니다. 여섯 번째 항은 3입니다.

해결 접근 방법

방법 1: 중첩 루프 사용

가장 직관적인 방법은 중첩 루프를 사용하는 것입니다. 바깥쪽 for 루프는 1부터 n까지 반복하고, 안쪽 루프는 1부터 i(바깥쪽 루프의 반복 변수)까지 반복합니다. 안쪽 루프의 각 반복마다 수열의 원소 개수를 세고(count), count가 n과 같아지는 순간 i 값을 반환하면 됩니다.

방법 2: 패턴 위치를 이용한 효율적인 접근

더 효율적인 방법은 수열의 패턴을 위치 관점에서 분석하는 것입니다. 각 원소가 수열에서 차지하는 위치는 다음과 같습니다.

원소 1: 위치 1
원소 2: 위치 2, 3
원소 3: 위치 4, 5, 6
원소 4: 위치 7, 8, 9, 10

각 원소가 마지막으로 등장하는 위치만 모아 보면 다음과 같은 수열을 얻을 수 있습니다.

1, 3, 6, 10, 15, 21, 28, …

즉, 숫자 x는 1 + 2 + 3 + … + (x−2) + (x−1)번째 항까지 나타납니다. 이를 일반화하면 다음과 같습니다.

n = x × (x − 1) / 2

양변에 2를 곱해 정리하면 2n = x² − x, 즉 x² − x − 2n = 0이 됩니다. 이차방정식의 근의 공식을 적용하면 다음과 같은 결과를 얻습니다.

x = (1 + √(1 + 8n)) / 2

이 공식을 활용하면 루프 없이 O(1) 시간 복잡도로 n번째 항을 즉시 계산할 수 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int findNthTerm(int n) {
    int x = (((1) + (double)sqrt(1 + (8 * n))) / 2);
    return x;
}
int main(){
    int n = 12;
    cout<<"The series is 1, 2, 2, 3, 3, 3, 4, 4, ...\n";
    cout<<n<<"th term of the series is "<<findNthTerm(n);
    return 0;
}

실행 결과

The series is 1, 2, 2, 3, 3, 3, 4, 4, ...
12th term of the series is 5

마무리

중첩 루프 방식은 최악의 경우 O(n²)의 시간 복잡도를 가지지만, 근의 공식을 활용한 방법은 O(1)로 상수 시간 안에 답을 구할 수 있습니다. 따라서 n이 매우 큰 경우에는 후자의 방법이 훨씬 효율적이며, 삼각수의 성질을 이용해 수열 문제를 수학적으로 단순화한 좋은 예시라 할 수 있습니다.