백준 2193 : 이친수(C++)

문제

풀이

1자리 이친수 : 1 -> 1개
2자리 이친수 : 10 -> 1개
3자리 이친수 : 100, 101 -> 2개
4자리 이친수 : 1000, 1010, 1001 -> 3개
5자리 이친수 : 10000, 10100, 10101, 10010, 10001 -> 5개

위 이친수들을 보면, 상위 2자리는 10으로 고정이고 나머지 자리들은 전, 전전 이친수들과 같습니다. 따라서 Dynamic Programming 점화식을 만들면
dp[i] = dp[i-1] + dp[i-2]입니다.
(피보나치 수열과 같습니다.)

코드

#include <iostream>
#include <math.h>

using namespace std;
// table : number of pinary number
long long dp[91];
int N;

void dynamicPinary() {
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 1;
    for(int i = 3; i <= N; i++) {
        dp[i] = dp[i-2] + dp[i-1];
    }
    cout << dp[N] << "\n";
}

int main() {
    cin >> N;

    dynamicPinary();
    return 0;
}