백준 2193 이친수

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 N자리의 이친수를 구하는 문제입니다. 이친수란 0으로 시작하지 않고 1이 연속해서 나오지 않는 숫자를 뜻합니다.

 

먼저 1자리의 경우를 보면 1 한가지만 가능합니다.

 

2자리인 경우도 10 으로 한가지만 가능합니다.

 

3자리인 경우는 101, 100 으로 두가지경우가 가능합니다.

 

4자리의 경우 1010, 1001, 1000 으로 세가지 경우가 가능합니다.

 

5자리의 경우를 보면 10100, 10101, 10010, 10001, 10000 총 5가지 경우가 가능합니다.

 

여기서 이제 규칙을 찾아보면 n자리의 경우 n-1자리의 모든경우에 0을 덧붙이는 경우는 가능합니다.  그렇다면 1을 덧붙일 수 있는 경우를 살펴 보아야하는데 1을 덧붙이기 위해선 앞에 0이 와야하고 그 경우는  n-2자리의 개수와 동일하다는 것을 알 수 있습니다.

 

따라서 n = n-1 + n-2 라는 점화식이 만들어지고 이는 피보나치 수열과 동일함을 알 수 있습니다. 따라서 dp를 이용하여 피보나치 수열을 만들어 주면 됩니다.

 

다음은 코드입니다.

 

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N;
	cin >> N;
	long long num[91] = {0, };
	num[1] = 1;
	num[2] = 1;
	
	for(int i = 3; i <= N; i++) 
		num[i] = num[i-1] + num[i-2];
	
	cout<<num[N];
	
	return 0;
}