백준[baekjoon] 26518

https://www.acmicpc.net/problem/26518

26518번: 수열의 극한값

문제풀이

$$a_i = b*a_{i-1} + c*a_{i-2} (i \geq 3)$$

수열 a가 주어졌을때

$$\lim_{n \to inf}\frac{a_n}{a_{n-1}}$$

값을 구하는 문제로써 문제에서 항상 이 값이 수렴되어짐이 보장되어 있다.

 

문제에서 주어지는 정수범위로 인해 순차적으로 수열값(a_n)을 구하면서 극한 값을 접근하는 시도는 long long int를 사용하더라도 오버플로우가 발생한다.

 

따라서 적절하게 식을 변형시켜 오버플로우를 방지해주어야 한다.

$$a_n = b*a_{n-1} + c*a_{n-2}, 양변에 a_{n-1} 나누기 $$

$$\lim_{n \to inf}\frac{a_n}{a_{n-1}} = b + c*\lim_{n \to inf}\frac{a_{n-2}}{a_{n-1}}$$

 

$$\frac{a_n}{a_{n-1}} 값이 x일때 \, \frac{a_{n+1}}{a_n}값은 b+\frac{c}{x}이다.$$

 

극한값이 수렴하니 n을 계속증가하여 일정한 값이 나올때까지 반복하면된다.

 

코드

#include<bits/stdc++.h>

using namespace std;

int main()
{
   ios_base::sync_with_stdio(0), cin.tie(0);

   int b, c, a1, a2;
   double past, cur;

   cin >> b >> c >> a1 >> a2;
   past = (double)a1/a2;

   cout << fixed;
   cout.precision(6);

   while(true) {
      cur = c/past + b;

      if((float)cur == (float)past) {
         cout << cur << '\n';
         break;
      }

      past = cur;
   }

   return 0;
}