[Baekjoon] 백준 2193번 이친수

2193번 이친수 문제 풀이

문제

• 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

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

• 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
  N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 N이 주어진다.

출력

• 첫째 줄에 N자리 이친수의 개수를 출력한다.

예제

입력
3 
---
출력
2

코드

#include<iostream>
using namespace std;

long long d[91][3];

int main() {
    int n;
    cin >> n;
    d[1][0] = 0;
    d[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 1; j++) {
            if (j == 0)
                d[i][j] += d[i - 1][0] + d[i - 1][1];
            if (j == 1)
                d[i][j] += d[i - 1][0];
        }
    }

    cout << d[n][0] + d[n][1] << '\n';
    return 0;
}

해결방법

• 0으로 시작할 수 없으니 d[1][1] = 1, d[1][0] = 0을 먼저 선언한다.

• 1이 연속해서 오면 안되는 것을 유의해서 점화식을 만들어 보면 d[i][0] = d[i-1][0] + d[i-1][1], d[i][1] = d[i-1][0]이 됨을 알 수 있다.

• 점화식을 세우지 않고 실제로 이친수를 만들어보면 d[1] = 1, d[2] = 1, d[3] = 2, d[4] = 3, d[5] = 5가 된다. 즉 피보나치수열 구하는 공식과 동일하다. d[n] = d[n-1] + d[n-2]

    int main() {
        int n;
        cin >> n;
        d[1] = 1;
        d[2] = 1;
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
  
        cout << d[n]<<"\n";
    }