[백준/C++] 이친수

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

이친수의 성질은 0으로 시작하지 않고, 1이 연속해서 나오지 않는 수를 의미한다.

N을 나열하면서 예를 적어보면서 점화식을 쉽게 찾을 수 있었다.N=1  →  1N=2  →  10N=3  →  100, 101N=4  →  1000, 1001, 1010N=5  →  10100, 10110, 10000, 10001, 10010

 

이친수의 성질에 의해서 반드시 처음 두자리 수는 1과 0이 차례로 오게되고, 이후에는 1이 올지 0이올지 경우를 나눠서 생각할 수 있다즉 N=5일때 첫 두자리는 1과 0이고 세번째 자리가 1인지 0인지 나눠서 생각해보면세번째 자리가 1일때의 경우의 수는 N=3일 때의 경우의 수와 같고세번째 자리가 0일때의 경우의 수는 N=2일 때의 경우의 수와 같다

따라서 점화식을 써보면

dp[i] = dp[i-2] + d[i-1] 로 피보나치수와 같은 점화식임을 알 수 있다.

 

한가지 주의해야할 점은 피보나치수가 46번째 항이 넘어가는 순간 int의 범위를 벗어나게되어 오버플로우가 발생함으로 자료형은 long long으로 dp배열을 선언해 주어야 한다. (해당 문제의 N 범위는 1~90)

 

#include <iostream>

using namespace std;

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