[2193] 이친수

• 입력: 자릿수 N (1≤N≤90)
• 출력: 자릿수 N개의 이친수의 개수
• 이친수 조건: 1) 0으로 시작하지 않는다 2) 연속으로 1이 나오지 않는다
• 풀이: 

피보나치를 이용해서 문제를 풀었는데, 우선 1개 자릿수의 이친수는 "1"로 한 개이고 2개 자릿수의 이친수는 "10"으로 한 개이다. (이하 n 자릿수의 이친수를 이친수(n))이라 하겠다.

이친수(3) 100, 101

이친수(4) 1000, 1001, 1010

이친수(5) 10000, 10001, 10010, 10100, 10101 

위와 같이 정해진다. 특징으로 무엇을 알 수 있냐면 이 이친수(n)는 이친수(n - 1)에는 0을 붙이고 이친수(n - 2)에 01을 붙인 것과 같다.

즉, 이친수(n) = 이친수(n - 1) + 이친수(n - 2) 로 피보나치 수열이다. 

최대 90까지 들어오기때문에 시간초과가 날 수 있으므로 다이나믹 프로그래밍을 이용해야한다.

• 알고리즘: 다이나믹 프로그래밍
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; #define ll long long vector<ll> dp(91, -1); ll fibonacci(int n) { if (n == 0) return 0; else if (n == 1) return 1; else if (dp[n] != -1) return dp[n]; else return dp[n] = fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n, t; scanf("%d", &n); printf("%lld\n", fibonacci(n)); return 0; }
• 문제 참고: https://www.acmicpc.net/problem/2193