알고리즘 :: 백준 :: DP :: 2193 :: 이친수

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
성질 1) 이친수는 0으로 시작하지 않는다.
성질 2) 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

문제접근

1. 우리가 사용할 수 있는 숫자는 1 또는 0 뿐임을 인지한다.

2. 숫자 길이 N에 대해 마지막 숫자가 1인 경우와 0인 경우를 나눠서 생각하면 다음과 같은 점화식을 도출할 수 있다.

3. 마지막 숫자가 0인 경우를 $D[n][0]$, 1인 경우를 $D[n][1]$
   이라고 한다면, $D[n][0] = D[n-1][0] + D[n-1][1]$이고, $D[n][1] = D[n-1][0]$이다.

4. 이 문제는 오직 0과 1 두 수로만 이뤄진 특별한 케이스이므로 2차원 DP를 사용하지 않고 1차원으로도 표현할 수 있다. 왜냐하면 마지막 숫자가 1인 경우 무조건 다음으로 올 수 있는 숫자가 0으로 정해지기 때문이다.

5. 따라서 점화식은 $D(n) = D(n-1) + D(n-2)$이다.

코드

#include <iostream>
using namespace std;
using ll = long long;

ll dp[91];
int N;

ll solve(int num) {
    if (num < 0) return 0;
    if (num == 0 || num == 1) return num;
    if (dp[num] > 0) return dp[num];
    return dp[num] = solve(num - 1) + solve(num - 2);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    cout << solve(N) << '\n';
}

결과