[BOJ/백준 2193][C++] 이친수

문제

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

백준 2193

 

문제 내용

n자리 이친수의 개수를 구하면 된다.

이친수란 아래와 같다.

1. 이친수는 0과 1로만 이루어져 있다.
2. 이친수는 0으로 시작하지 않는다. (== 1로만 시작한다.)
3. 이친수에서는 1이 두 번 연속으로 나오지 않는다.

 

 

문제 풀이

dp로 해결할 수 있는 문제이다.

dp[i][0]은 마지막이 0으로 끝나는 i자리 이친수,

dp[i][1]은 마지막이 1로 끝나는 i자리 이친수로 설정해 두고 문제를 풀었다.

 

0으로 끝나는 이친수는 이전까지의 이친수가 1로 끝나든 0으로 끝나든 상관이 없다.

하지만, 1로 끝나는 이친수는 이전까지의 이친수가 반드시 0으로 끝나야 한다.

 

+) 배열을 int로 선언하면 오버플로우가 발생하기 때문에, long long으로 선언해야 한다.

 

코드

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long dp[n + 1][2];
    dp[1][0] = 0; // 0으로 끝나는 1자리 이친수
    dp[1][1] = 1; // 1로 끝나는 1자리 이친수

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

    cout << dp[n][0] + dp[n][1];
}