C++에서 급수 a, b, b, c, c, c…의 N번째 항을 찾는 프로그램

문제 개요

이 문제에서는 하나의 숫자 N이 주어지며, 우리의 과제는 C++로 수열 a, b, b, c, c, c…의 N번째 항을 찾는 프로그램을 작성하는 것입니다.

문제 설명

다음 수열의 N번째 항을 구해야 합니다.

a, b, b, c, c, c, d, d, d, d, …(총 N개의 항)

즉, 주어진 수열의 일반항을 찾아내야 합니다.

입력 예시

N = 7

출력 예시

d

해결 접근 방법

수열의 일반항을 찾으려면 먼저 수열의 패턴을 자세히 관찰해야 합니다. 이 수열은 'a'가 1개, 'b'가 2개, 'c'가 3개, 'd'가 4개씩 나타나는 구조로, 각 문자의 반복 횟수가 1씩 증가합니다. 따라서 특정 위치까지의 전체 항 개수는 등차수열(AP)의 합으로 표현할 수 있습니다.

등차수열의 합 공식은 다음과 같습니다.

합 = (n/2) × (a + (n-1)d)

첫째 항 a = 1, 공차 d = 1이므로, n번째 문자까지의 누적 항 개수는 아래와 같이 정리됩니다.

n번째 문자까지의 항 개수 = (n/2) × (1 + (n-1)×1)
                      = (n/2) × n
                      = n(n+1)/2

이 누적 개수가 처음으로 N 이상이 되는 n이 곧 N번째 항에 해당하는 문자를 나타냅니다. 식을 변형하면 n의 근삿값을 다음과 같이 구할 수 있습니다.

n ≈ √(2N)

따라서 N번째 항의 문자는 기준 문자 'a'에 n을 더한 값, 즉 ('a' + n)으로 간단히 계산할 수 있습니다.

구현 예제

#include <iostream>
#include <math.h>
using namespace std;
char findNTerm(int N) {
    int n = sqrt(2*N);
    return ((char)('a' + n));
}
int main() {
    int N = 54;
    cout<<N<<"th term of the series is "<<findNTerm(N);
    return 0;
}

실행 결과

54th term of the series is k

위 코드는 N = 54를 입력했을 때 수열의 54번째 항이 'k'라는 결과를 출력합니다. sqrt 함수로 √(2N)의 값을 구한 뒤 정수형으로 변환하고, 그 값을 기준 문자 'a'에 더해 원하는 문자를 얻는 방식입니다. 이처럼 등차수열의 합 공식을 활용하면 반복문 없이도 O(1)의 시간 복잡도로 N번째 항을 빠르게 계산할 수 있다는 점이 이 접근 방법의 가장 큰 장점입니다.