이 문제에서는 하나의 정수 값 N이 주어지며, 우리의 과제는 다음 수열의 n번째 항을 찾는 것입니다.
0, 0, 2, 1, 4, 2, 6, 3, 8, 4, 10, 5, 12, 6, 14, 7, 16, 8, 18, 9, 20, 10…
예시를 통해 문제를 이해해 보겠습니다.
입력 − N = 6
출력 − 2
해결 접근 방법
수열의 n번째 항을 구하려면 먼저 수열을 면밀히 관찰해야 합니다. 이 수열은 두 개의 하위 수열이 홀수 번째와 짝수 번째 위치에 교차하여 배치된 형태입니다. 각각 살펴보겠습니다.
짝수 번째 위치의 경우
- T(2) = 0
- T(4) = 1
- T(6) = 2
- T(8) = 3
- T(10) = 4
n이 짝수일 때 T(n)의 값은 {(n/2) − 1}이라는 규칙을 따릅니다.
홀수 번째 위치의 경우
- T(1) = 0
- T(3) = 2
- T(5) = 4
- T(7) = 6
- T(9) = 8
n이 홀수일 때 T(n)의 값은 {n − 1}이라는 규칙을 따릅니다.
즉, 홀수 번째 항은 해당 위치에서 1을 뺀 값이 되고, 짝수 번째 항은 위치를 2로 나눈 뒤 1을 뺀 값이 됩니다. 이 두 규칙만 알면 별도의 반복문 없이 O(1) 시간 복잡도로 n번째 항을 바로 계산할 수 있습니다.
예제 코드
다음은 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.
#include <iostream>
using namespace std;
bool isEven(int n){
if(n % 2 == 0)
return true;
return false;
}
int findNthTerm(int n){
if (isEven(n))
return ((n / 2) - 1);
else
return (n - 1);
}
int main(){
int N = 45;
cout << N << "번째 항의 값은 " << findNthTerm(N);
return 0;
}
실행 결과
45번째 항의 값은 44
코드 설명
isEven() 함수는 입력값이 짝수인지 판별하고, findNthTerm() 함수는 짝수 여부에 따라 적절한 공식을 적용합니다. N = 45는 홀수이므로 n − 1 = 44가 반환되어 결과가 출력됩니다. 이 풀이법은 상수 시간에 동작하므로 매우 큰 N에 대해서도 효율적으로 처리할 수 있습니다.