백준 2193번 : 이친수

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

문제읽기

다이나믹 프로그래밍. 우선 시작해보자.
0과 1로만 이루어진 수를 이진수라고 한다. 이진수 중 특별한 성질을 갖는 것들이 있는데 이들을 이친수, pinary number이라고 한다. 처음 듣네.
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 연속 2번 나타나지 않는다. 11을 부분 문자열로 갖지 않는다는 뜻이다.

N자리 이친수의 개수를 구해보자.

---

이거 저번의 2579번 : 계단 오르기가 떠오르는 문제인데 접근 시작해보자.

공비가 $3^{a+b}*2^{a}$ 로 나온다. 와^^

코드

#include <iostream>
using namespace std;

int main() {
	int N;
	cin >> N;

	long long arr[91];
	arr[1] = 1;
	arr[2] = 1;

	for (int i = 3; i <= N; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	cout << arr[N];
	return 0;
}

분석

우선 내가 헛짓거리한 것 먼저 정리해보자. 우선 1로 시작했을 때의 가지와 0으로 시작했을 때의 가지를 계산하였다. 그리고 이거를 3자리 로 묶어 총 몇개가 나오는지 확인하였고 이를 점화식으로 엮으려고 했다. 나머지가 1과 2가 나오는 경우를 각각 계산하여 추가적으로 가지를 늘려주려고 했다. 의미 없는 짓이였지만^^

처음에 접근을 잘못한게 있다. 1-1이 불가능한데 1-1-(0/1)를 포함했으니 수가 이상하게 나왔지..

계산 잘 하자. 할 말이 없다. 경우의 수를 잘 세자..

점화식은 쉽게 나왔다.

long long arr[91];
arr[1] = 1;
arr[2] = 1;

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

여기서 주목해야 할 것은 long long으로 arr를 선언했다는 것이다. int가 엄청나게 길어질 것 같으면 int가 아닌, long long으로 선언해야 한다는 것. 그래서 실제로 한 번 틀린 것은 int로 선언해서 그런 것이다. 9자리 수를 넘을 것 같다면 바로 long long으로 바꾸자. 생각해보니 90자리 수인데 int로 담으려고 했던 내가 바보다.