[백준/BOJ/C++] 2193번 이친수 - Dynamic Programming

이미지를 클릭하면 문제 링크로 이동합니다.

1. 문제

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

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

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

---

2. 입력

첫째 줄에 N이 주어진다.

---

3. 출력

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

---

4. 풀이

문제를 풀기에 앞서 N에 따라 나올 수 있는 이친수를 나열해보았다. 

이친수를 나열한 다음, 2번째 규칙인 '11을 부분 문자열로 갖지 않는다.'를 고려해보면 이친수가 가지는 규칙성을 파악할 수 있다. 이친수는 1로 시작해야 하는데 11은 부분 문자열로 가질 수 없기 때문에 가장 앞자리 두 숫자는 10이 될 수밖에 없다. 따라서, 10 뒤에 따라오는 숫자들만 고려해보도록 한다.

위의 그림에서 빨간색 네모 박스를 먼저 살펴보자. N이 4일때 앞에 10을 제외하면 00, 01, 10으로 구성이 되는데 이는 N이 3일 때와 N이 2일 때 모든 숫자가 구성으로 갖고 있는 숫자와 동일하다.

다음으로 파란색 네모박스를 살펴보면, 앞서 규칙과 동일하게 N이 5일 때 000, 001, 010, 100, 101로 구성되는데 4와, 3에서 모든 숫자들의 구성과 동일하다.

따라서, N에 따른 이친수의 개수를 저장하는 배열을 dp라고 할 때, dp[i] = dp[i - 1] + dp[i - 2] 라는 식을 도출할 수 있게 된다.

---

5. 소스코드

#include <iostream>
using namespace std;
int main(){
    int N; //N 자리
    cin>>N; 

    long dp[91] = {0,};
    dp[0] = 0; dp[1] = 1;
    for(int i = 2; i < N+1; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    cout<<dp[N];
}