[백준] 2193번

💻 C++ 기반

이친수
https://www.acmicpc.net/problem/2193

1. 테이블 정의하기
   dp[i][j] : i번째 수가 j일 때 만들어질 수 있는 이친수의 개수
2. 점화식 찾기
   i-1번째 숫자가 0이면 i번째에 0 또는 1이 올 수 있음
   i-1번째 숫자가 1이면 i번째에 0만 올 수 있음
   ➡️ 아래 코드 참고
3. 초기값 정하기
   dp[1][1] = 1
   dp[2][0] = 1
   ➡️ 둘다 어떤 상황이든 항상 동일한 값이 나와서 그냥 i가 2일 때도 초기값을 선정

#include <cstdio>

#define MAX_N 91

using namespace std;

long long dp[MAX_N][2];

int main()
{
    int N;
    scanf("%d", &N);

    dp[1][1] = 1;
    dp[2][0] = 1;
    for (int i = 3; i <= N; i++)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
    }
    printf("%lld", dp[N][0] + dp[N][1]);
    return 0;
}