글 읽기 - 이게 왜 피보나치?

wjddydgns99 4년 전 2

저는 자릿수 저장해서 dp로 풀었는데요. 풀고나서 질문게시판 보니 피보나치가 좀 보여서요.

이런 문제가 피보나치임을 발견하신 분들은 하나씩 대입해봐서 규칙을 찾은 건가요?

만약 그렇게 했다면 n=5정도까지 한 다음 규칙 보여서 바로 피보나치인가? 하고 돌려보니 정답이었던것인가요?

어떻게 이 문제를 보고 피보나치라는걸 바로 알죠??

질문게시판 보고 좀 놀랐네요...
어떻게 그런 생각을 했죠...? 궁금합니다...!!

첨부 코드는 저의 소스입니다..

#include<iostream>//내풀이

using namespace std;

long long a[91][2];
int main()
{
	a[1][1] = 1;//첫번째 자리는 1
	int n; cin >> n;
	for (int i = 2; i <= n; i++)
	{
		a[i][0] += a[i - 1][0] + a[i - 1][1]; // i번째 0이 들어가는 경우 += i-1번째가 0 또는 1
		a[i][1] += a[i - 1][0]; // i번째 1이 들어가는 경우 += i-1번째가 0 
	}
	cout << a[n][0] + a[n][1] << "\n";
	return 0;
}

ho94949 4년 전 5

DP 식을 잘 살펴 보시면, a[i][0] = Fi, a[i][1] = Gi 라고 쓰면,
코드를 Fi = F(i-1) + G(i-1)Gi = F(i-1)이라고 작성하셨는데,
G(i-1) = F(i-2) 이므로, 결국 점화식이 Fi = F(i-1) + F(i-2)가 됩니다.

evenharder 4년 전 4

피보나치 수열이 나타나는 유명한 형태입니다.

f(i)를 길이 i의 이친수의 개수라고 하면 f(1) = 2, f(2) = 3이 성립합니다.

길이 i의 수열은 맨 끝이 0이거나 1입니다.

0인 수열인 나머지 자리를 채우는 경우의 수인 f(i-1)개 있습니다.
1인 수열은 뒤에서 두 번째 수가 0이 되어야 하므로 숫자 2개가 고정되어 f(i-2)개 있습니다.

이를 합하면 f(i) = f(i-1) + f(i-2)가 성립하고, 피보나치 수열의 점화식과 동일합니다.

wjddydgns99 4년 전 1

아 모두 빠르고 친절한 답변 감사합니다.

정리해보니깐 맞네요...

신기합니다 dp,,,

감사합니다....!!

evenharder 4년 전 3

지문을 잘못 읽어서 보충 설명하겠습니다. 첫 자리가 1이므로 둘째 자리가 0이 되어야 합니다. 그러므로 이친수는 10xxx 꼴이 됨을 알 수 있습니다.

이 xxx꼴에 대해 논리를 전개하면 제가 말한 초깃값과 점화식이 나옵니다.

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

문제

문제

출처

ICPC

이게 왜 피보나치?

wjddydgns99 4년 전 2

ho94949 4년 전 5

evenharder 4년 전 4

wjddydgns99 4년 전 1

evenharder 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말