[백준] 2193번 이친수

2193번: 이친수

동적계획법으로 풀었다.

i번째 0의 개수 = i - 1번째 0의 개수 + i - 1번째 1의 개수

i번째 1의 개수 = i - 1번째 0의 개수

 

i번째에 1이 나오려면 i-1번째에 0일 수밖에 없다. i-1번째가 1이면 i번째가 1이면 안되니까. (연속으로 1이 나오면 안 되니까)

i번째에 0이 나오려면 i-1번째가 0이든 1이든 상관없다. 0이 연속으로 나오는 것은 상관 없으니까.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	long* zero = new long[n];
	long* one = new long[n];
	zero[0] = 0;
	one[0] = 1;
	for (int i = 1; i < n; i++) {
		zero[i] = zero[i - 1] + one[i - 1];
		one[i] = zero[i - 1];
	}
	cout << zero[n - 1] + one[n - 1];
	return 0;
}