BOJ 2193번: 이친수

문제

문제 바로가기> BOJ 2193번: 이친수

2193번: 이친수

 

풀이

dp[N][0] : N자리 수 이찬 수 중 0으로 끝나는 수

dp[N][1] : N자리 수 이찬 수 중 1로 끝나는 수

 

0으로 끝나는 수는 0과 1이 뒤에 붙을 수 있다.

1로 끝나는 수는 0이 뒤에 붙을 수 있다.

 

이 점을 이용해서 dp로 문제를 해결했다!

 

#include<iostream>
#define MAX 91
using namespace std;

long long dp[MAX][2];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N; cin >> N;
	dp[1][0] = 0;
	dp[1][1] = 1;
	for (int i = 2; i <= N; i++) {
		dp[i][0] = dp[i - 1][1] + dp[i - 1][0];
		dp[i][1] = dp[i - 1][0];
	}
	cout << dp[N][0] + dp[N][1];
}