백준 2193 번 - 이친수(C++/DP/Dynamic Programming)

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

접근법

문제를 읽자마자 DP로 풀어야 겠단 생각이 들었다.

 

일단 두가지 규칙이 주어졌다.

1. 이친수는 0으로 시작할 수 없다

2.  연속되는 1을 가질수 없다.

 

일단 개수를 구하라는 문제이며, 

 

1일때 1 (1개)
2일때 10 (1개)
3일때 100, 101(2개)
4일때 1000, 1001, 1010(3개)

 

위 패턴을 볼때 확실한 규칙이 있었다.

예를들어, 길이가 1일때는 이친수가 1 하나 밖에 없다. (1번규칙 이친수는 0으로 시작할 수 없으므로)

그 다음, 길이가 2일때는 10 하나밖에 없다. (2번규칙 이친수는 연속되는 1을 가질수 없으므로)

길이가 3일때는 100, 101 2개이다.

길이가 4일때는 1000,1001,1010 3개이다.

 

여기서 길이가 4일때를 기준으로 보자. 

이전에 길이가 3일때는 100, 101이 있었는데, 

100뒤에는 0또는 1 어떤수가 와도 상관이 없어 1000, 1001 이 되지만,

101뒤에는 0밖에 오지 못한다 (1011은 2번 규칙위배)

 

4자리 수일때는

끝이 0으로 끝나는 경우는 3자리 수일때 1로 끝나는 경우 + 3자리 수일때 0으로 끝나는 경우

끝이 1로 끝나는 경우는 3자리수 일때 0으로 끝나는 경우

 

이렇게 정리된다.

이를 코드로 표현하면

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

이다.

초기값만 dp[0][0], dp[0][1] 로 설정해주면 이친수의 개수를 구해준다

 

 다만 입력이 90이 들어오면  output은 2880067194370816120이므로, int, long형으로는 턱도없다.

나는 long long 형을 사용해서 자료의 크기를 맞춰주자.

(보통 값이 큰 문제는 나머지를 구하라 하는데 여긴 그냥 출력이다.) 

 

코드

#include <iostream>

using namespace std;

long long dp[91][2];

int main()
{
    int N;
    cin >> N;
    dp[0][0] = 0;
    dp[0][1] = 1;


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