[백준 #2193] 이친수 (C++)

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

2193번: 이친수

 

이 문제는 다이나믹 프로그래밍을 사용해 풀었다.

 

n이 1일 경우 한자리 이친수의 개수 = 1 (1)

n이 2일 경우 두 자리 이친수의 개수 = 1 (10)

n이 3일 경우 세 자리 이친수의 개수 = 2 (100, 101)

n이 4일 경우 네 자리 이친수의 개수 = 3 (1000, 1001, 1010)

n이 5일 경우 다섯 자리 이친수의 개수 = 5 (10000, 10001, 10010, 10100, 10101)

 

이렇게 작은 부분부터 풀어나가면 피보나치 수열임을 알 수 있다.

따라서, dp[n] = dp[n-1]+dp[n-2]가 된다.

 

#include <iostream>
using namespace std;

long long dp[91] = { 0, 1, 1 };

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

	int n;
	cin >> n;

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

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