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

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

문제

[조건]

1. 1로 시작
2. 11이 부분 문자열로 올 수 없음.

 

그림으로 그려보니

dp[i] = d[i-1] + d[i-2] 라는 점화식이 나오는 걸 발견했다.

 

왜 이런 결과가 나왔을까 생각해봤다.

0은 그 뒤에 0과 1이 올 수 있고, 1은 뒤에 0만 올 수 있다.

 

4자리 이친수를 찾아보면 다음과 같다.

3번째 자리의 0과 1에서 부터 0, 1, 0이 뻗어나와야 하고,

이는 2번째 자리에서 3번째 자리를 유도하는 방식과 일치한다.

 

3번째 자리의 0에서부터 0, 1이 뻗어나와야하고,

이는 1번째 자리에 2번째 자리를 유도하는 방식과 일치한다.

 

따라서, 위와 같은 점화식( dp[i] = d[i-1] + d[i-2] )이 유도된다.

 

 

 

풀이

#include <bits/stdc++.h>
using namespace std;

vector<long long> dp(91);

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    dp[1] = 1, dp[2] = 1;

    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n];
}