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

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다.

---

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

2

 

---

풀이과정

문제를 어떻게 접근을 해야할지 계속 고민을 하다가 뭔가 규칙성을 가지고 있을 거 같아서 경우의 수를 적어보게되었다.

형식으로 이루어져있고 개수를 보면

피보나치의 수열과 같은 규칙성을 가지고 있는것을 확인할 수 있어서 code를 작성할때도 똑같이 규칙을 적용시켜서 작성하게 되었다.

a[i + 1] = a[i] + a[i - 1]

code

#include <iostream>

int		main(void)
{
	long long n;
	long long a[91] = {0,};

	std::cin >> n;
	a[0] = 0;
	a[1] = 1;
	a[2] = 1;
	for(int i = 2; i <= n; i++) {
		a[i + 1] = a[i] + a[i - 1];
	}
	std::cout << a[n];

	return (0);
}

---

후기

오늘 푼 문제와 같이 점화식이 숨겨져있는 문제들은 코테 같은 것들을 볼때 어떻게 접근을 해야할지 모르겠다.

운이 좋으면 점화식이 있을 수도 있는거고 아니면 아예 규칙성이 없는 문제일 수도 있는데.

규칙성없는 문제를 점화식이 있다고 생각을 하고 계속 규칙성만 찾으려고 하다가 오랜시간이 지나버리면 그만큼 손해로 다가오게되고,

그렇다고 점화식이 없다고 가정을 하고 문제의 접근을 하게 되면 점화식을 가지고 푸는것보다 코드가 복잡해지고 시간 복잡도가 더 가중이되니 점화식이 있는지 없는지를 빠르게 판단할 수 있는 요령을 길러야할 거  같다.