Coding Test - cpp/DP
[백준 2193: 이친수 ] - C++
에드윈H
2021. 1. 20. 16:58
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;
long long dp[91][2] = {
{0, 0} //0
,{0, 1} //1
,{1, 0} //2
};
cin >> n;
for (int i = 3; i <= n; i++)
{
dp[i][0] = dp[i - 1][0] + dp[i - 1][1]; //이전이 0으로 끝나는수라면 0과 1을 붙인수 만큼 추가
dp[i][1] = dp[i - 1][0]; //이전이 1로 끝나는수는 이전의 0붙는 수만큼 추가
}
cout << dp[n][0] + dp[n][1];
return 0;
}