[백준] 다이나믹 프로그래밍 - 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자리 이친수의 개수를 출력한다.

 

예제 입력1

3

 

예제 출력1

2

 

생각

n = 1

1 

n = 2

10 

n = 3

100    101

n = 4

1000    1001    1010       

n = 5

10000    10001    10010    10100    10101   

n = 6

100000    100001    100010    100100    101000    100101    101001    101010   

n = 7

1000000    1000001    1000010    1000100    1001000    1001001    1010000

1000101    1001010    1001001    1010100    1010010    1010001    1010101

 

p[n] = p[n-1] + p[n-2] 으로 식을 세울 수 있다.

 

 

처음에 범위를 생각하지 못하고 int 형 배열로 두고 제출했더니 실패했었다. 문제를 풀다보니 01타일 문제가 생각이 났다.

 

※ 피보나치 수 구하는 공식과도 같은데, 피보나치 수의 경우 46번째 수가 2971215073 이 되어 int 의 범위를 초과한다. 

그래서 01타일 문제 2020/02/12 - [알고리즘/문제풀이] - [백준] 동적계획법 - 1904. 01타일 에서도 int형 범위를 넘어가기 때문에 %15746 을 해줘서 범위를 초과하지 않게 해주는 것이었다. 

여기서는 long long int 로 int 이상의 자료형을 사용해야한다. 

 

 

 

작성한 코드

 

#include <iostream>
 
using namespace std;
 
int n;
long long int d[91];
 
int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    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";
    
    return 0;
}