[백준 2193] 이친수

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

2193번: 이친수

길이가 1인 이친수는 한가지이다.

 

1

 

길이가 2인 이친수도 한가지이다.

 

10

 

길이가 3인 이친수는 두가지이다.

 

100

101

 

길이가 4인 이친수는 세가지이다.

 

1000

1001

1010

 

길이가 5인 이친수는 다섯가지이다.

 

10000

10001

10010

10100

10101

 

...

 

---

 

계속 해보면 알겠지만

 

n-1번째 이친수의 갯수와 n번째 이친수의 갯수에 연관성이 존재한다.

 

n-1번째 이친수 중에서

 

1. 0으로 끝나는 친구들은 n번째에서 0과 1을 모두 붙일 수 있다.

 

2. 1로 끝나는 친구들은 n번째에서 0만 붙일 수 있다.

 

---

 

따라서 0으로 끝나는 이친수와 1로 끝나는 이친수의 개수를 각자 저장해야한다.

 

그러면 점화식은 1번과 2번을 통해서 쉽게 구할 수 있다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(void){
	long long n;
	long long dp[2][100]; //0이면 전에 0 1이면 전에 1

	cin >> n;

	dp[1][0] = 1;
	dp[0][0] = 0;

	for (int i = 1; i < n; i++){
		dp[0][i] = dp[0][i - 1] + dp[1][i - 1];
		dp[1][i] = dp[0][i - 1];
	}

	n -= 1;
	cout << dp[0][n] + dp[1][n] << endl;

	return 0;
}