[백준] 26015 : Enjoyable Entree

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

문제 분석

 문제는 전날과 전전날의 스프를 같은 양으로 합쳐서 매일 새로운 스프를 만들때, N번째 날의 스프의 재료의 비율을 묻는 문제이다. 재료는 두가지 뿐이므로 첫번째 재료의 양만 구하면 나머지는 100에서 해당 재료를 빼면 된다. n번쨰 날 1번째 재료의 양과 2번째 재료의 양을 $A_n, B_n$이라 할때 문제는 다음과 같은 식을 만족한다.

$A_n=\frac{A_{n-1}+A_{n-2}}{2}$
$A_n+B_n=100$
$A_1=100, A_2=0$
오차범위는 $10^{-6}$

 여기서 n의 범위가 $[1,10^{18}]$이므로 0부터 순차적으로 A를 구하는 것은 어렵다. 따라서 가능한 접근 방식은 하단의 두가지이다. 문제 해결전략에서 두가지 방식 모두로 풀어보겠다. 

방법 1 : 애드 훅 방식으로 앞의 몇개의 수를 나열 시켜버린다.
방법 2 : 점화식을 풀어버려서 일반식을 만들어버린다.

문제 해결 전략

 방법 1 : 애드훅

일단 일반화할 방법을 잘 모르겠으면 나열하고 보자 유서깊은 방식이다. 일단 A만 기술하겠다. 12번째 까지만 해도 대충 특징이보인다.  우선 A가ㅏ 33.3을 기준으로 진동을 하면서 수렴을 하는 양상을 보인다. 여기까지만 봐도 수렴의 신뢰를 가지고 오차범위내에서 진동시 멈추는 방법도 존재한다.

더 확실히 하려면 전 항과의 차이가 $-100*(-1/2)^{n-2}$인것을 확인가능하다. 여기서 부터는 일반식으로 가도 좋고 아니면 전항과의 차이가 오차범위 내일때만 고려 해도 좋다.

N	A	$A_n-A_{n-1}$
1	100	-
2	0	-100
3	50	50
4	25	-25
5	37.5	12.5
6	31.25	-6.25
7	34.375	3.125
8	32.8125	1.5625
9	33.59375	0.78125
10	33.203125	0.390625
11	33.398438	0.1953125
12	33.300781	0.09765625

 방법 2 : 점화식 풀기

 점화식 풀이는 아래의 방식을 따라가면된다. 그러면 N에대해서 일반식을 맨아래와 같이 구할 수 있다. 실제코드상에서는 삼항연산자와 등비수열의 합으로 간략화시켰다. 

$A_n=\frac{A_{n-1}+A_{n-2}}{2}$
$2*(A_n-A_{n-1})=-(A_{n-1}-A_{n-2})$
$2*R_n=-R_{n-1}$
$R_n=R_2*(-1/2)^{n-1}(n > 1)$ 

$A_n-A_{n-1}=(-100)*(-1/2)^{n-1}$
$A_n=A_{n-1}-100*(-1/2)^{n-1}$
$A_n=100+\sum_{k=2}^{N}-100*(-1/2)^{k-2}(N>2), A_1=100$

코드

 방법 1 : 애드훅

#include <iostream>
#include <vector>
#include <math.h>
#include <iomanip>


using namespace std;

int N;

int main()
{
    vector<float> ratio={100.0f,0.0f};

    while(abs(ratio[ratio.size()-2]-ratio[ratio.size()-1]) > 1e-8) ratio.push_back((ratio[ratio.size()-1]+ratio[ratio.size()-2])/2.0f);

    cin >> N;
    
    cout << fixed << setprecision(-6) << ratio[min(N,(int)ratio.size())-1] << " " << 100.0f - ratio[min(N,(int)ratio.size())-1] << '\n';
}

 방법 2 : 점화식 풀기

#include <iostream>
#include <math.h>
#include <iomanip>


using namespace std;

int N;

int main()
{
    cin >> N;
    float temp = N==1? 100.0 : 100.0 - 200.0/3.0*(1.0-pow(-0.5,N-1));
    cout << fixed << setprecision(-6) << temp << " " << 100.0f - temp << '\n';
}