투 명 테 잎

풀다보니 신기한 형상을 발견했다.
이 문제가 피보나치 수열과 관련이 있다는 것을 발견한것이다!

첫 항을 a, 두 번째항을 b라고 놓으면
a, b, a-b, 2b-a, 2a-3b, 5b-3a, 5a-8b ... 의 순서로 이어진다.
여기서
두 번째항부터
항의 값이 다음항의 값보다 클 조건을 구해보면
b >= 1/2a
b <= 2/3a
b >= 3/5a
b <= 5/8a 처럼
분자, 분모가 피보나치 수열과 관련있게 전개됨을 알 수 있다!
(피보나치 수열은 1, 1, 2, 3, 5, 8, ... 으로 전개된다.)

또한, 이 조건을 만족하는 b의 범위를 위의 부등식으로 축소 할 수 있다.
두 개 씩 묶어서 사용하면
1/2a <= b <= 2/3a
3/5a <= b <= 5/8a 처럼
점점 범위가 축소된다.

피보나치 수열을 계속 진행하면서
범위를 축소해나가다가
a와 b의 차이가 1이하이면
그 때, 우리가 원하는 b값을 구할 수 있다.

ps)
이번 문제 1등은 코드 사이즈가 많이 작다.
내가 제출한 최종코드보다도 185바이트나 작다.
시간은 서버가 안정할 때 제출하면
0.1초 단축할 수 있을거 같지만
코드사이즈는 줄이기 어려워 보여서
경과 시간 3등
코드 사이즈 19등으로 만족하고 넘어가야겠다. 

#include 
using namespace std;
typedef int U;
typedef double D;
U F[]={1,2,3,5,8,13,21,34,55,89,144,233,377},i,r[17];
D n,s,e,c;

int main()
{
	cin >> n;
	do
	{
		s = n * F[i] / F[i+1];
		e = n * F[i+1] / F[i+2];
		if (e - s < 1)
		{
			s = U(s+0.5);
			break;
		}
	}while(i+=2);
	r[0] = n;
	r[1] = s;
	i = 2;
	do
	{
		r[i] = r[i-2] - r[i-1];
	}while (r[i++] >= 0);
	cout << --i << endl;
	c=i;
	i=0;
	while(i < c)
	{
		cout << r[i] << " ";
		i++;
	}

	return 0;
}

#include 
using namespace std;typedef int U;typedef double D;U F[]={1,2,3,5,8,13,21,34,55,89,144,233,377},i,r[17];D n,s,e,c;int main(){cin>>n;do{s=n*F[i]/F[i+1];e=n*F[i+1]/F[i+2];if(e-s<1){s=U(s+0.5);break;}}while(i+=2);r[0]=n;r[1]=s;i=2;do{r[i]=r[i-2]-r[i-1];}while (r[i++]>=0);cout<<--i<