문제 출처

1. 문제설명

• 0과 1로만 이루어진 수가 있다.
• 이친수는 다음의 성질을 만족한다.
  • 0으로 시작하지 않는다.
  • 1이 두 번 연속으로 나타나지 않는다.
• N자리의 이친수 개수를 구하라

2. 알고리즘 설계

• DP 문제이다.
• 규칙을 찾아보자
  • 1 : 1
  • 2 : 10
  • 3 : 100, 101
  • 4 : 1000, 1001, 1010
• N-1번째, N-2번째 개수의 합과 같다.
• 즉, DP[i] = DP[i-1] + DP[i-2]
  • 피보나치 수열과 같은 점화식

3. 전체 코드

#include<bits/stdc++.h>
using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long DP[91] = { 0, };
	DP[1] = 1;
	DP[2] = 1;

	int n; cin >> n;
	for (int i = 3; i <= n; i++)
		DP[i] = DP[i - 1] + DP[i - 2];

	cout << DP[n];
	return 0;
}