#2193 이친수

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

2193번: 이친수

실버 3 문제이다. 연등할때 그다음날 하루종일 고민할 문제를 빈종이에 써가는데, 어제는 이문제를 써갔었다. 근데 예상외로 너무 쉬워서 그냥 뚝-딱 풀어버렸다.

 

//2022-04-18 BOJ 2193
#include <iostream>
#include <algorithm>
using namespace std;

int n;
long long cnt;
long long dp[91][3];

int main()
{
  //freopen("input.txt","r",stdin);

  cin>>n;
  dp[1][0]=0;
  dp[1][1]=1;

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

  cout<<cnt<<'\n';
}

점화식을 구성해보자.

길이가 N이고 마지막 수가 L이라고 가정한다. 이때 L은 0과 1 두가지밖에 없다.

__ __ __ ... __ __ L  -> 길이가  N

__ __ __ ... __ 0또는 1  -> 길이가 N-1

여기서 L이 1이라면 L이전에 오는 수는 1일 수 없다. L이 0이라면 L이전에 오는 수는 0또는 1이 될수 있다.

이를 토대로 점화식을 구성해보면, dp[N][1] = dp[N-1][0]  ,  dp[N][0] = dp[N-1][1] + dp[N-1][0] 가 된다.

 

이때 길이가 1인 이친수는 1 하나뿐이므로 dp[1][0]=0, dp[1][1]=1 이 된다. 이후로 for문을 돌리면서 점화식을 그대로 써주고 마지막에는 길이가 n인 이친수 개수를 모두 더해야 하므로 cnt에 더해주었다.