문제 개요
이 문제에서는 하나의 정수 N이 주어지며, 우리의 목표는 다음 수열의 N번째 항을 구하는 것입니다.
14, 28, 20, 40, 32, 64, 56, 112…
예시를 통해 문제를 살펴보겠습니다.
입력:
N = 6
출력:
64
접근 방법
수열의 N번째 항을 구하려면 먼저 수열의 일반항을 파악해야 하며, 이를 위해서는 수열을 면밀히 관찰해야 합니다. 다행히 이 수열은 두 가지 서로 다른 방법으로 해결할 수 있습니다.
방법 1: 홀수·짝수 위치별 분석
이 수열은 홀수 번째 위치와 짝수 번째 위치에서 각각 다른 규칙을 따르는 두 수열이 결합된 형태입니다.
홀수 위치의 항들: 14, 20, 32, 56, …
T1 = 14
T3 = 20 = T1 + 6
T5 = 32 = T3 + 12
T7 = 56 = T5 + 24 = T1 + 6 + 12 + 24 = T1 + 6 × (1 + 2 + 4)
TN = T1 + 6 × (20 + 21 + 22 + … + 2((N/2)−1))
짝수 위치의 항들: 28, 40, 64, 112…
T2 = 28
T4 = 40 = T2 + 12
T6 = 64 = T4 + 24
T8 = 112 = T6 + 48 = T2 + 12 + 24 + 48 = T2 + 6 × (2 + 4 + 8)
TN = T2 + 6 × (21 + 22 + … + 2((N/2)−1))
이를 일반화하면 수열의 N번째 항은 다음과 같습니다.
TN = Ts + 6 × Σ 2((N/2)−1) (s부터 N까지 2씩 증가하며 합산)
- N이 짝수일 때: s = 2
- N이 홀수일 때: s = 1
예제 코드
#include <iostream>
#include <math.h>
using namespace std;
long findNthAdd(int s, int i, int n){
int sum = 0;
for(; i <= n; i += 2){
sum += pow(2, (int)((i/2) - 1));
}
return 6 * sum;
}
long findNthTermSeries(int n){
int s, i;
if(n % 2 == 0){
s = 28;
i = 4;
} else {
s = 14;
i = 3;
}
return (s + findNthAdd(s, i, n));
}
int main(){
int n = 15;
cout << n << "번째 항은 " << findNthTermSeries(n);
return 0;
}
출력:
15번째 항은 776
방법 2: 인접 항 간의 관계 활용
또 다른 방법은 현재 항이 이전 항의 두 배이거나, 항의 위치가 홀수인 경우 이전 항보다 8 작다는 규칙을 이용하는 것입니다.
N이 짝수인 경우: TN = 2 × T(N-1)
N이 홀수인 경우: TN = T(N-1) − 8
따라서 2부터 N까지 반복하면서 각 위치가 짝수인지 홀수인지 판별하고, 그에 맞는 연산을 적용하면 원하는 항을 차례로 계산할 수 있습니다.
예제 코드
#include <iostream>
using namespace std;
bool isEven(int N){
if(N % 2 == 0)
return true;
return false;
}
int findNthTermSeries(int n){
int TermN = 14;
for (int i = 2; i <= n; i++) {
if (isEven(i))
TermN *= 2;
else
TermN -= 8;
}
return TermN;
}
int main(){
int n = 15;
cout << n << "번째 항은 " << findNthTermSeries(n);
return 0;
}
출력:
15번째 항은 776
마무리
두 방법 모두 시간 복잡도는 O(N)으로 동일하지만, 방법 2는 pow 함수 호출 없이 단순한 곱셈과 뺄셈만 사용하므로 실제 실행 속도가 더 빠르고 코드도 직관적입니다. 반면 방법 1은 수열의 수학적 구조를 명확하게 드러내 준다는 장점이 있어, 일반항을 유도하는 과정 자체를 학습하고자 할 때 유용합니다.