백준 2193번 이친수

이친수 성공분류

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

57925

23149

17226

38.159%

문제

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자리 이친수의 개수를 출력한다.

#include <iostream>

using namespace std;

int n;
long long DP[100];

int main() {
    cin >> n;

    DP[0] = 0;
    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;
}

한자리수의 이친수 = 1
두자리수의 이친수 = 10
세자리수의 이친수 = 100, 101
네자리수의 이친수 = 1000, 1001, 1010

위와 같이 앞 두자리수 10은 고정이다(1로 시작해야하고 11처럼 연속으로 1이 등장하면 안되기 때문)
그렇다면 이친수의 갯수를 정하는 기준은 앞 두자리를 제외한 나머지 자리라는 것을 알 수 있다.
이때 규칙이 등장하는데 네자리수의 이친수를 보면 뒷자리가 두자리수의 이친수 마지막 두자리 + 세자리수의 이친수 마지막 두자리로 조합되어 있다는 것을 알수있다. ( 10, 01, 00 )
이에 따라 다섯자리수의 이친수는 2개 + 3개로 총 5개가 된다고 유추할 수 있다. 이를 점화식으로 세워보면

DP[n] = DP[n-1] + DP[n-2]

이 식을 이용하여 간단하게 풀어주면된다. 
※ 이친수의 갯수가 후반에 급격히 늘어나 int의 범위를 넘어서게 되므로 long long타입을 써주어야한다.
(이거때문에 한번 틀림 ㅜㅜ)