백준 2193 풀이

링크텍스트

간단한 문제였다.

0으로 시작할 수 없고 11이 나올 수 없기 때문에 간단하게 풀이 할 수 있었던것 같다.

F(1) = 1, F(2) = 1, F(3) = 2 ... 이런 식으로 하나씩 증가해서 규칙을 찾을 수 있다.

n==4 일 때, F(3)일 때 경우의 수 101, 100에서 1 또는 0을 덧붙임으로 구할 수 있다. 이 때 101에서는 1을 붙일 수 없기 때문에 1010밖에 될 수 없고 100은 2가지 다 가능하다. 따라서 n==4일 때는 3이다.

n==5 일 때, F(4)의 경우의 수 1010, 1001, 1000 에 1또는 0을 붙이면 10101, 10100, 10010, 10001, 10000 총 5개이다.

이전 단계에서 구한 이진수에서 끝이 1로 끝나는 경우 하나의 경우만 가지고 그 외에는 각각 2개의 경우의 수를 가진다.
그런데 여기서 경우의 수의 변화를 잘 살펴보면
결국 F(n) = F(n-1)+F(n-2)와 같다는 사실 또한 알 수 있다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
using namespace std;

int t;
int n;
int m;
long long arr[91];

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

	cin >> n;

	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 1;
	arr[3] = 2;

	for (int i = 4; i <= n; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	
	cout << arr[n] << '\n';
	return 0;
}