백준 2193번 이친수 C++

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

 

 맨 뒷자리가 0으로 끝날때와 1로 끝날때를 나눠서 생각했다.

0으로 끝날때는 다음에 1이나 0 아무거나 와도 되고, 1로 끝날때는 0만 와야한다.

dp[i][0]=dp[i-1][0]+dp[i-1][1]

dp[i][1]=dp[i-1][0]

이 점화식을 이용해서 문제를 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<vector<ll>> dp(n + 1, vector<ll>(2));
	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];
};