문제

코드

#include <iostream>
using namespace std;
long long d[91][2];
int main()
{
   int n;
   cin>>n;
   d[1][1]=1;
   d[1][0]=0; 
    for(int i=2;i<=n;i++)
    {   
        for(int j=0;j<=1;j++)
        {   
            d[i][j]=0;
            if(j==0)
            {
                d[i][j]+=d[i-1][1]+d[i-1][0];
            }
            if(j==1)
            {
                d[i][j]+=d[i-1][0];
            }
        }
    }
    long long sum=0;
    for(int i=0;i<2;i++)
    {
     sum+=d[n][i];
    }
    cout<<sum<<"\n";
    return 0;
}

풀이

d[i][L] = i자리 수와 L로 끝나는 이친수의 개수
L은 0,1 만 올수있으므로

L이 0 일떄

d[i][0] 에 d[i-1][0] 와 d[i-1][1] 를 더해줌
0 앞에는 0과 1이 올수 있기 때문

L이 1 일떄

d[i][1] 에 d[i][0] 을 더해줌
1앞에는 0만 올수있기 때문에