[C++][백준] - 이친수 (2193번)

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

2193번: 이친수

🔔 문제 : 

 

이친수의 개수를 출력하는 문제입니다.

---

🔔 Kick Point :

DP 문제이고,  0의 개수에 집중하면 됩니다.

 

F(x) 가 x의 0의 갯수라고 생각하면

F(k) = 2* F(k-2)  + F(k-3) 이라는 식이 나옵니다.

 

또한 G(x)가 x의 이친수의 갯수라고 생각하면

G(x) = F(x+1) 이라는 식을 알 수 있습니다.

 

 

이는 G(k) = G(k-1) + G(k-2) 라는 식으로도 사용 할 수 있습니다.

 

---

🔔 Code :

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

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

	vector<long long> dp(n + 1);
	dp[1] = 1;
	dp[2] = 1;


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

	cout << dp[n];
}

 

---