글 읽기 - 9009 피보나치 그리디 알고리즘 증명?

wxogus25 7년 전 1

제목 그대로 9009 피보나치 문제를 큰 수부터 선택하는 방식으로 풀었습니다.

그런데 어째서 이 문제가 그리디 알고리즘으로 풀리는지는 모르겠네요

그래서 나름대로 정당성(?)을 증명해보겠다고 몇번 끄적거리기는 했지만 결국 해내지 못했습니다...

수학고수님들 이 문제 좀 해결해주세요!

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <deque>
#include <functional>

using namespace std;

int fibo[100];
stack <int> s;

int main()
{
	int t, n, i, c;
	fibo[1] = 1;
	for (i = 2; fibo[i - 1] <= 1000000000; i++)
	{
		fibo[i] = fibo[i - 1] + fibo[i - 2];
	}
	cin >> t;
	while (t--)
	{
		cin >> n;
		while (n != 0)
		{
			c = lower_bound(fibo + 1, fibo + 46, n) - fibo;
			if (fibo[c] > n) c--;
			n -= fibo[c];
			s.push(fibo[c]);
		}
		while (!s.empty())
		{
			cout << s.top() << " ";
			s.pop();
		}
		cout << endl;
	}
}

koosaga 7년 전 12

https://en.wikipedia.org/wiki/Zeckendorf%27s_theor...

에 의하면 항상 두개의 연속한 피보나치 수를 포함하지 않는 유일한 표현 방법이 존재함을 증명할 수 있습니다. (증명 읽어보세요) 지금 사용하신 알고리즘이 저 표현방식을 반환합니다.

그렇다면, 저러한 표현 방식이 왜 최소 수를 사용할까요? 만약에 두개의 연속한 피보나치 수를 포함하는 방법이 더 최소라고 생각을 해보면, 그 두개의 연속한 수 Fi, Fi+1 을 묶어서 Fi+2로 줄일 수 있습니다. 최소라고 했음에도 그보다 더 효율적인 표현 방식을 찾았으니 가정에 모순이고, 즉 최소의 표현 방식은 두개의 연속한 피보나치 수를 포함하지 않습니다. 그러한 표현 방법은 위에서 언급했듯이 유일하게 존재합니다.

wxogus25 7년 전 1

@koosaga

와.... 한번에 이해가 가는 설명이네요 그렇게 간단하게 증명할 수 있다니 감탄이 저절로 나오네요

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9009 피보나치 그리디 알고리즘 증명?

wxogus25 7년 전 1

koosaga 7년 전 12

wxogus25 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말