[C++] 백준 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자리 이친수의 개수를 구하는 프로그램을 작성하시오.

 

2193.cpp

#include <iostream>

long long d[91] = {0,};

long long pinary_num(int N) {
    if (N <= 2)
        return 1;
    if (d[N] != 0)
        return d[N];
    d[N] = pinary_num(N-1) + pinary_num(N-2);
    
    return d[N];
}

int main(int argc, const char * argv[]) {
    
    int N;
    std::cin >> N;
    
    std::cout << pinary_num(N);
    
    return 0;
}

카메라 포커스는 무시하도록...

이번주 디피 유형의 문제들을 계속 bottom up으로만 풀어서 탑다운의 재귀 + dp로 풀어보았다

처음에 잘못생각해서 이런걸 문제로 내나 싶었는데 그건 아니었다 ㅎㅎ;

dp 문제는 결국 ☆점화식☆을 찾아야 하고, 특히 이 문제는 그걸 찾는게 초큼 재밌었다

사진 오른쪽 빨간 부분이 핵심 아이디어인데(아이디어라기보단 규칙성 찾은거...) 이전 단계의 0의 개수가 이번 단계의 1의 개수가 되고, 이전 단계의 1의 개수와 0의 개수의 합이 이번 단계의 0의 개수가 된다. (0의 개수, 1의 개수라 함은 사진 위쪽 가운데 부분에서 볼 수 있듯이 N자리에 대한 경우의 수에서 끝나는 숫자를 말하며 0 뒤에만 1이 올 수 있기 때문에 그러한 규칙이 완성된다)

그리고 잊을만하면 나오는 long long은 기억하도록 하자 ~(이번에는 문제에서 알려준 범위인 90을 입력해봤다가 음수가 나와서 깨달았다 ^&)