[BOJ] 2193 이친수

Link https://www.acmicpc.net/problem/2193

Note

0으로 시작하지 않으면서 1이 연속으로 두번 나오지 않는 N 자리의 이진수의 개수를 구하는 문제

각각의 경우를 계산 해보면
1 : 1 ( 1개 )
2 : 10 ( 1개 )
3 : 100 101 ( 2개 )
4 : 1000 1001 1010 ( 3개 )
5 : 10000 10001 10010 10100 1010 1 ( 5개 )

피보나치 수열이다
아래의 점화식을 이용하자

dpTable[i] = dpTable[i - 1] + dpTable[i - 2]; ( 단 i > 1 )

소스코드

#include <iostream>

using namespace std;

const int MAX = 90;

int main()
{
	int tc;
	long long int dpTable[MAX + 1] = { 1, 1, };

	cin >> tc;

	for (int i = 2; i < MAX + 1; i++)
		dpTable[i] = dpTable[i - 1] + dpTable[i - 2];

	cout << dpTable[tc-1]<< endl;

	return 0;
}

연관 문제

1003 - 피보나치 수열 ( https://www.acmicpc.net/problem/1003 ) 
2019-01-14 11:00:00에 Tistory에서 작성되었습니다.