[ 백준 1904 ] 01타일 (C++)

백준의 01타일(1904) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

몇 가지 예시들을 통해서 문제를 해결해보자. 지금부터는 간단하게 표현하기 위해서 다음과 같은 수식을 이용해서

표현할 것이다. F[A] = B 라는 수식을 사용할 것인데, F[A] = B의 의미는 "길이가 A인 2진 수열의 경우의 수는 B개 입니다." 를 의미한다.

#Case1 : N = 1

가장 먼저, 길이가 1인 경우이다. 주어진 타일이 '00'과 '1' 이 있고, '00' 그 자체만으로도 길이가 이미 2인 타일이기 때문에

길이가 1인 2진 수열은 '1' 하나 뿐이다.

F[1] = 1

#Case2 : N = 2

길이가 2인 2진수열로는 '00' 타일을 하나 사용하는 경우와 '1'타일을 2개 사용하는 경우 즉 ! '00', '11'과 같이 2가지 경우가 존재한다.

F[2] = 2

#Case3 : N = 3

길이가 3인 2진수열을 살펴보자.

먼저 발생 가능한 모든 경우를 다 적어보면 다음과 같은 경우들이 존재한다.

1. 001

2. 111

3. 100

이렇게 총 3가지 경우가 발생한다.

여기서부터는 그냥 넘어가지말고 하나의 특징만 조금 살펴보고 가보자.

먼저, 위에서 이야기한 1번(001)과 2번(111)을 보게되면, 하나의 공통점이 있다.

"001", "111" 에서 빨강색으로 칠해진 부분을 잘 살펴보자. 어디서 본 놈들인가 했더니, 우리가 위에서 알아보았던 Case2(N = 2) 에서 구했던 놈들이다. 즉 ! 1번과 2번은 "길이가 2인 2진 수열에서, 뒤에 '1'을 추가적으로 붙인 경우" 라는 것이다.

하지만 3번은 아니다. 3번에서 가장 앞에 2개의 숫자를 보면 '10' 인데, 이는 N = 2에 속하지 않은 놈이었다.

3번은 가장 앞에 숫자만 보면 '1'이 있는데, 이 '1'은 길이가 1인 2진수열(Case1)에서 구했었던 2진수열에 뒤에 '00' 타일이 하나 더 추가적으로 붙은 꼴이다. 이정도만 알고 다음 케이스로 넘어가보자.

F[3] = 3

#Case4 : N = 4

먼저 발생 가능한 모든 경우들을 다 적어보자.

1. 0011

2. 1111

3. 1001

4. 0000

5. 1100

위와 같이 5가지 경우가 존재한다.

그럼 또 특징을 한번 살펴보자. 위에서 1 ~ 3번 경우를 한번 살펴보자.

"0011", "1111", "1001" 을 보면, 공통적으로 Case3(N = 3)에서 구했었던 빨강색 부분에다가 뒤에 '1'타일을 추가적으로 붙인 놈들이라는 것을 알 수 있다.

즉 ! 이 3가지 경우는, Case3의 경우의 수를 그대로 가져온다는 것이다. 그리고 그 경우에 뒤에 '1'만 추가적으로 붙이는 것이다.

4번과 5번 경우를 한번 살펴보자.

4번과 5번은 위에서 언급한 3가지 경우처럼 "0000", "1100" 빨강색 부분이 Case3에서 나온 경우들이 아니다.

왜냐하면 절대 그럴 수가 없는 게, 가장 마지막 숫자가 '0'으로 끝나는데, '0'은 그 하나만으로 타일을 이룰 수 없기 때문에

가장 마지막에 '0'이 오는 꼴로 만들기 위해서는, 최소 2칸이 보장되어야 한다는 것이다. 왜냐하면 '00'이 가장 마지막에 와야지만, 가장 마지막을 '0'으로 끝낼 수가 있기 때문이다.

그럼, 2칸을 남겨놓고 앞에 2개의 숫자들을 한번 봐보자. "0000", "1100" 여기서는 하나의 공통점을 발견할 수 있다.

바로 빨강색으로 표시된 "00"과 "11"은 우리가 Case2(N = 2)에서 구했었던 2진 수열이라는 것이다.

즉 ! N = 4인 2진 수열의 갯수는 N = 3인 2진 수열의 갯수 + N = 2인 2진 수열의 갯수로 이루어진다는 것을 알 수 있다.

정리해보자.

N = K인 2진 수열의 갯수를 구하기 위해서 우리는 크게 2가지로 구분할 수가 있다.

1. 가장 마지막이 '1'로 끝나는 길이가 K인 2진 수열

2. 가장 마지막이 '0'으로 끝나는 길이가 K인 2진 수열

먼저, 가장 마지막이 '1'로 끝나는 2진 수열을 만들기 위해서는, 길이가 K - 1인 2진 수열에서 뒤에 '1'만 추가적으로 덧붙이면 되는 꼴이기 떄문에, 길이가 K - 1인 2진 수열의 갯수를 가지게 된다.

두 번째로, 가장 마지막이 '0'으로 끝나는 2진 수열을 만들기 위해서는, 가장 마지막 2개의 숫자가 '00'으로 끝나야 하는 형태이고, 그러기 위해서는 길이가 K - 2 인 2진 수열에서 뒤에 '00'만 추가적으로 덧붙이면 되는 꼴이 된다.

즉 ! 길이가 K - 2인 2진 수열의 갯수를 가지게 되는 것이다.

따라서 N = K인 2진 수열의 갯수를 일반화된 식으로 적어보면

F[K] = F[K - 1] + F[K - 2] 가 된다는 것을 알 수 있다.

이를 점화식으로 문제를 해결할 수 있다.

실제 코드에서는, 우리가 사용했던 수식인 F[]를 표현할 수 있도록 1차원 배열을 하나 만들어서 사용해 주었다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1000010
#define MODULER 15746
using namespace std;
 
int N;
int DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[1] = 1;
    DP[2] = 2;
    for (int i = 3; i <= N; i++)
    {
        DP[i] = DP[i - 2] + DP[i - 1];
        DP[i] = DP[i] % MODULER;
    }
    cout << DP[N] % MODULER << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}