BOJ 2193 이친수

문제출처 : https://www.acmicpc.net/problem/2193

1. 문제요약

- 0과 1로 이루어진 수 중에 0으로 시작하지 않고 1이 두번 연속으로 나타나지 않는 수를 이친수

- 1, 10, 101 등은 이친수

- 01, 110 은 이친수가 아님

- n자리 이친수의 갯수는?

- 1 <= n <= 90

2. 접근방법

- n자리 이진수를 브루트 포스로 다 확인할 수 없음.

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 0

- d[n][i] 를 n자리수, 마지막 수가 i인 이친수의 갯수라고 하면

  d[n][0] = d[n-1][0] + d[n-1][1]

  d[n][1] = d[n-1][0]

- 조금만 더 생각을 해보면

- n자리가 0이면, n-1 자리는 0, 1

  n자리가 1이면, n-1 자리는 무조건 0 이므로 n-2 자리에 0, 1

- d[n] 을 n자리수 이친수의 갯수라고 하면

  d[n] = d[n-1] + d[n-2]

  피보나치

3. 시간복잡도

- n

4. 회고

- 이친수의 갯수가 int형을 넘을 수 있으므로 long long

소스코드

#include<iostream>
using namespace std;

int n;
long long d[100] = { 0, 1 };

int main(void){
	cin >> n;
	for (int i = 2; i <= n; i++){
		d[i] = d[i - 1] + d[i - 2];
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]