이친수 (백준 - 2193번)

동적 계획법을 이용하는 문제였다.

 

규칙을 먼저 살펴 보도록 하겠다.

 

1자리

-> 1

=> 1개

 

2자리 

-> 10

=> 1개

 

3자리

-> 100, 101

=> 2개

 

4자리

-> 1000, 1001, 1010

=> 3개

 

5자리

-> 10000, 10001, 10100, 10101, 10010

=> 5개

....

 

피보나치 수열과 같은 규칙을 보이고 있다.

F[i] = F[i - 2] + F[i - 1]

 

하지만 90자리 까지 구한다는 점에 주의를 하자. 90자리까지 표현하려면 int 범위로는 부족하기 때문이다. 

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main()
{
	unsigned long long dp[90 + 1];
	int input; 
	cin >> input;

	dp[0] = 0; dp[1] = 1; dp[2] = 1;
	for (int i = 3; i <= input; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	cout << dp[input] << endl;
}