백준 2193 - 이친수

문제

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

2193번: 이친수

 

풀이

N번째 자리에 올 수 있는 수는 0 또는 1이다.

○ ○ ○ .... ☆ ● 에서

만약 ●에 0이 온다면 ☆에는 0 또는 1이 올 수 있다. 따라서 n-1에 오는 수에 따라 개수가 결정이 된다.

반대로 ●에 1이 온다면 ☆에는 0만 올 수 있다. 따라서 n-2에 오는 수에 따라 개수가 결정이 된다.

 

D[N] = N자리 이친수의 개수라고 하면 다음과 같은 점화식을 구할 수 있다.

D[N] = D[N-1] + D[N-2]

 

코드

#include <iostream>
 
using namespace std;
 
int N;
long long dp[91];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    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];
 
    return 0;
}
 

 

#include <iostream>
 
using namespace std;
 
int N;
long long dp[91][2];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    dp[1][0] = 0; dp[1][1] = 1;
    dp[2][0] = 1; dp[2][1] = 0;
 
    for (int i = 3; i <= N; i++)
    {
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
    }
 
    cout << dp[N][0] + dp[N][1];
 
    return 0;
}