[C++] 백준 1904 - 01타일

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

1904번: 01타일

 

1. 입력

\(1 \le N \le 1,000,000 \)인 자연수 \(N\)

 

2. 출력

00 타일과 1 타일로 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지

 

3. 풀이

문제를 풀며 다음을 고려했다.

 

1. 길이가 N 이하인 이진 수열의 개수가 아닌 길이가 N인 수열의 개수를 요구하고 있다.
2. 0 타일은 존재하지 않으므로, N이 2만큼 증가할 때 적용되는 경우의 수는 3개로 압축할 수 있다.(1, 00, 11)

 

그런데 2번을 잘 생각해 보면, 실제로는 N+2더라도 11은 제외해도 되는 수라는 것을 알 수 있다. N+1일 때 이미 1이 적용되므로, N+2는 00에 더해 단순히 N+1에서 다시 1을 적용하면 그만이기 때문이다.

 

그럼 문제로 돌아가서, 조건을 만족하는 2진 수열을 나열해 보면 다음과 같다.

N	이진 수열
1	1
2	00, 11
3	001, 100, 111
4	0000, 0011, 1001, 1100, 1111

색상으로 강조된 부분을 보면 규칙을 어렵지 않게 발견할 수 있다.

 

표를 보면, 길이가 N인 이진 수열의 개수는 길이가 N-2인 이진 수열의 앞에 00을 붙인 수열의 개수와 길이가 N-1인 이진 수열의 앞에 1을 붙인 수열의 개수의 합으로 정리된다. 즉, 상관 관계를 다음과 같이 정리할 수 있다.

 

\[f(N) = f(N-2) + f(N-1)\]

 

뭔가 익숙한 향기가 난다. 점화식은 피보나치 수열과 동일하며, 값은 피보나치 수열에서 N을 1만큼 뺐을 때와 동일하다. 즉, N=2일 때 1 대신 2를 출력하는 부분만 수정한 피보나치 수열을 구현하는 것으로 문제를 해결할 수 있다. 문제에서는 시간 제한을 설정하고 있으므로, 시간 복잡도를 고려한 알고리즘을 구현해야 한다.

 

최종적으로 아래와 같이 구현했다.

 

#include <iostream>

int NumOfTile(int num);

int main()
{
    int N;
    std::cin >> N;

    std::cout << NumOfTile(N);

    return 0;
}

int NumOfTile(int num)
{
    if (num < 3)
        return num;
    int prev_prev = 1; // N - 2
    int prev = 2; // N - 1
    int now = 0;
    for (int i = 3; i <= num; i++)
    {
        now = (prev_prev + prev) % 15746;
        prev_prev = prev;
        prev = now;
    }
    return now;
}