(c++)백준 2193번: 이친수

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

2193번: 이친수

1. 0은 첫번째 자리에 올 수 없다.

2. 1은 앞에 0이 있어야 나올 수 있다.

 

※점화식※

dp[i][j] : i번째 자리가 j일 때 이친수 개수

dp[1][0] = 0 (첫번째 자리에 0 올 수 없다.)

dp[1][1] = 1

dp[x][0] = dp[x-1][0] + dp[x-1][1] (x번째 자리에 0이 오면 그 앞은 0과 1 모두 있을 수 있다.)

dp[x][1] = dp[x-1][0] (x번째 자리에 1이 오면 그 앞은 0만 있을 수 있다.)

 

#include <iostream>
using namespace std;

int N;
long long dp[91][2];

void DP() {
	dp[1][0] = 0;
	dp[1][1] = 1;
	for (int i = 2; i <= N; i++) {
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}
	cout << dp[N][0] + dp[N][1] << endl;
}

int main() {
	cin >> N;
	DP();
	return 0;
}