BaekJoon 2193 이친수

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

소스결과 1984 KB / 0 ms

출처 Backjoon

언어 C++ 17

분류 다이나믹 프로그래밍

 

설명

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 )