BOJ 2193번: 이친수

문제 설명

이친수의 조건:
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하기

🔗 문제 링크

핵심 아이디어

1. 맨 뒤에 0을 추가하는 경우
   • 이전에 0으로 끝난 숫자
   • 이전에 1로 끝난 숫자
2. 맨 뒤에 1을 추가하는 경우
   • 이전에 0으로 끝난 숫자 (1로 끝난 숫자는 1이 연속되어 안됨!)

코드

#include <bits/stdc++.h>
using namespace std;
int n;
int d[95][2]; // d[n][0] 은 0으로 끝나는 숫자, d[n][1]은 1로 끝나는 숫자

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    d[1][0] = 0; d[1][1] = 1;
    for(int i = 2; i <= n; i++){
        d[i][0] = d[i-1][0] + d[i-1][1]; // 이전 숫자에서 0을 추가
        d[i][1] = d[i-1][0]; // 이전 숫자에서 1을 추가
    }
    cout << d[n][0] + d[n][1];
}