Week 4 (Dp) - 문제 2193번 (이친수)

문제:

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력1:

3

예제 출력1:

2

코드:

#include <iostream>

using namespace std;

/*
이친수에 대하여

N자리 이친수는 N번째에는 1이 와야하며,
N-1번째에는 0이 와야한다.
다음 오는 N-2번째 자리가 1이면, 이친수 N-2자리
경우 수를 구하는 거와 마찬가지이다.
또한 0이면, N-3자리 경우 수를 구하는 거와 마찬가지이다.
아래로 쭉 내려가면서 경우의 수를 다 더하면 되지 않을까?
*/

/*
이 문제가 Dp인 이유

피보나치와 비슷하다.
답을 구하기 위해선 N보다 아래인 경우들을 다 더해야 하는데,
그 경우들 또한 거기에서 쪼개진 작은 경우들을 다시 다 구해야한다.
따라서 그냥 재귀를 사용한다면, 시간복잡도가 급격하게 커진다.
위에서 설명하였듯이 부분 반복 문제가 적용되며,
그 값들을 배열에 저장하고 사용하는 최적부분 구조를
둘 다 만족하기 때문에 Dp인 것이다.
*/

long long ar[91];       //답을 저장할 공간 (Dp 풀이 방식)

//Top-Down 방식을 채용
long long solution(int n)     //설명 생각하고 구현한 함수
{
    long long temp=0;

    if (n == 1 || n == 2)       //기저 상태 만들기
        return ar[n] = 1;

    if (ar[n] > 0)              //이미 저장된 경우, 값이 바로 출력
        return ar[n];

    for (int i = 1; i <= n - 2; i++)    
    {
        temp += solution(i);        //모든 경우의 수 다 더하기(재귀)
    }
    
    ar[n] = temp + 1;       //처음 1을 제외한 나머지 뒤가 다 0일때

    return ar[n];
}

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

    int N;
    cin >> N;       //N 선언 후 입력받기

    cout << solution(N);        //답 출력

    return 0;
}

설명:

주석 참고