개념
수열 bn이 다음과 같은 반복 관계로 정의되어 있다고 가정해 보겠습니다.
b1 = 1, bn+1/bn = 2n
이때 우리의 목표는 주어진 n에 대해 log2(bn)의 값을 구하는 것입니다.
입력 예시 1
6
출력
15
설명: log2(bn) = n(n-1)/2 = (6 × 5) / 2 = 15
입력 예시 2
200
출력
19900
풀이 방법
주어진 반복 관계는 다음과 같습니다.
bn+1/bn = 2n
같은 방식으로 n을 하나씩 줄여가며 식을 나열하면 다음과 같습니다.
bn/bn-1 = 2n-1
bn-1/bn-2 = 2n-2
…
b2/b1 = 21
위의 모든 등식을 좌변끼리, 우변끼리 각각 곱하면 분자와 분모가 서로 약분되어 다음과 같은 결과를 얻습니다.
(bn+1/bn) · (bn/bn-1) · … · (b2/b1) = 2n + (n-1) + … + 1
따라서 다음이 성립합니다.
bn+1/b1 = 2n(n+1)/2
여기서 지수 부분은 1부터 n까지의 합 공식, 즉 1 + 2 + 3 + … + n = n(n+1)/2를 활용한 것입니다.
초깃값이 b1 = 1이므로 다음과 같이 정리할 수 있습니다.
bn+1 = 2n(n+1)/2
이제 식에서 (n+1)을 n으로 치환하면,
bn = 2n(n-1)/2
양변에 밑이 2인 로그를 취하면 최종적으로 아래와 같은 간단한 닫힌 형태(closed form)의 공식을 얻습니다.
log2(bn) = n(n-1)/2
덕분에 실제로 거대한 수 bn을 직접 계산할 필요 없이, 이 공식만으로 O(1) 시간 복잡도에 답을 구할 수 있습니다.
C++ 구현 예제
// 주어진 반복 관계의 n번째 항을 구하는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// 필요한 값을 반환하는 함수
int sum(int n1){
// 공식을 이용해 답을 계산합니다.
int ans1 = (n1 * (n1 - 1)) / 2;
// 답을 반환합니다.
return ans1;
}
// 드라이버 코드
int main(){
// n 값을 설정합니다.
int n = 200;
// 함수를 호출하여 결과를 출력합니다.
cout << sum(n);
return 0;
}출력
19900
정리
반복 관계가 주어졌을 때 여러 단계의 식을 나열한 뒤 전체를 곱하는 망원급수(telescoping) 기법을 사용하면, 복잡해 보이는 점화식도 로그를 취했을 때 n(n-1)/2라는 단순한 다항식 형태로 귀결됩니다. 이렇게 유도한 공식을 사용하면 어떤 큰 n에 대해서도 상수 시간 안에 즉시 답을 계산할 수 있다는 점이 이 문제의 핵심입니다.