[백준/c++] BOJ 2193 - 이친수

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

2193번: 이친수

 

문제 설명

이진수 중 특별한 성질을 갖는 것들이 있는데, 이를 이친수라고 한다.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다.

N (1< = N <= 90) 이 주어졌을 때, N자리 이친수의 개수를 구한다.

해결

구해야 하는 것: 길이가 N인 이친수의 개수

dp[n][0] : 길이가 n인 0으로 끝나는 이친수의 개수

dp[n][1] : 길이가 n인 1로 끝나는 이친수의 개수

 

먼저 접근하기 어려우니 숫자들을 쓰면서 규칙성을 찾아 보자.

 

위 표를 보면 알 수 있듯이, 1로 끝나는 것은 길이 N - 1의 0으로 끝나는 이친수 뒤에 1을 붙인 것과 같다. 1로 끝나는 이친수에 1을 붙이면 이친수 특징 2번을 만족시키지 못하기 때문이다.

따라서 dp[N][1] = dp[N - 1][0] (이전 길이의 0으로 끝나는 이친수의 개수와 같음)

 

하지만 0은 1로 끝나는 이친수, 0으로 끝나는 이친수에 모두 붙일 수 있다.

dp[N][0] = dp[N - 1][0] + dp[N - 1][1] (이전 길이의 1, 0으로 끝나는 이친수의 개수의 합과 같음)

 

전체적으로 길이 N인 이친수의 개수는 dp[N][0] + dp[N][1]로 구하면 된다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n;
long long dp[100][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    cout << dp[n][0] + dp[n][1];
}