[C++] 백준 2193번 이친수

다이나믹 프로그래밍 문제입니다.

 

문제의 규칙으로는

1. 0과 1로만 이루어져 있습니다..

2. 0으로 시작하지 않습니다.

3. 1이 두번 연속 나타나지 않습니다.

와 같은 규칙을 가지고 있습니다.

 

이때 N자리 이친수의 개수를 출력하는 문제입니다.

1부터 차례대로 결과값을 생각해보면

1 - 1

2 - 10

3 - 100, 101

4 - 1000, 1001, 1010

5 - 10000, 10001, 10010, 10100, 10101

...

와 같이 값이 나옵니다.

여기서 규칙을 찾을 수 있습니다.

 

1 = 1개

2 = 1개

3 = 2개

4 = 3개

5 = 5개

6 = 8개

7 = 13개

 

n = n-1 + n-2의 모양인 피보나치 수열의

모습을 가지고 있는것을 확인할 수 있습니다.

 

arr[i] = arr[i-1] + arr[i-2]

를 밑에서부터 해주면서

값을 찾아낼때까지 반복하여 결과값을 도출해냈습니다.

 

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
    int n;
    cin >> n;
    long long int arr[100] = {0, };
    arr[1] = 1;
    arr[2] = 1;
    for(int i=3; i<=n; ++i){
        arr[i] = arr[i-1] + arr[i-2];
    }
    cout << arr[n];
    return 0;
}