백준 1904 01타일

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

1904번: 01타일

 

 

 

EXPLANATION

 

길이 1인 수열: 1

길이 2인 수열: 11, 00

길이 3인 수열: 111, 100, 001

길이 4인 수열: 1111, 1100, 1001, 0011, 0000

 

이렇게 풀면 한도 끝도 없겠다.

문제를 그렇게 내진 않았겠으니

규칙을 찾아야 한다.

 

 

 

본론부터 말하면, 

(길이가 N인 수열을 만들 수 있는 경우의 수)

= (길이가 N - 1인 수열을 만들 수 있는 경우의 수) + (길이가 N - 2인 수열을 만들 수 있는 경우의 수) 

 

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

 

 

 

길이가 N - 1인 수열에서 1을 추가하면 길이가 N인 수열이 된다.

길이가 N - 1인 수열에서 길이가 N인 수열을 만들 수 있는 경우는 이 경우 밖에 없다.

 

길이가 N - 2인 수열에서 길이가 N인 수열을 만들 수 있는 경우는 00, 11을 추가하는 이 두 경우가 있다.

그러나 N - 2에서 11을 추가하는 경우는 길이 N -1 수열에서 N이 수열을 만드는 경우에 포함된다.

 

길이 N - 3부터 그것보다 작은 길이 수열으로부터

길이가 N인 수열을 만들 수 있는 모든 경우는 위에서 구해진 경우에 포함된다.

그럴 확인하기 위해서 아까 우리가 나열했던 길이가 1인 수열에서 부터 4인 수열을 확인해보자.

길이 1인 수열: 1
길이 2인 수열: 11, 00
길이 3인 수열: 111, 100, 001
길이 4인 수열: 1111, 1100, 1001, 0011, 0000

길이가 4인 수열을 만들 때 길이가 3(4 - 1), 2(4 - 2)인 수열에서 만들어지는 경우를 파악하고

길이가 1(4 - 3)인 수열에서 만들어지는 경우를 보면

길이 1 수열에서 만들어지는 경우는 길이 3, 2 수열에서 만들어 지는 경우에 포함되는 것을 쉽게 확인할 수 있다.

 

 

출력 조건

첫 번째 줄에 지원이가 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력한다

DP[N]이 아니라 DP[N]%15746을 구해야 한다.

 

이것을 어떻게 구현하는 지 아래 예를 통해서 설명하겠다.

fib(1) = 1

fib(2) = 1

fIb(3) = 2 = 1 + 1

fib(4) = 3 = 2 + 1

fib(5) = 5 = 3 + 2

fib(5)%3 = 2

 

 

fib(1)%3 = 1%3 = 1

fib(2)%3 = 1%3 = 1

fib(3)%3 = ( fib(1)%3 + fib(2)%3 )%3 = (1 + 1)%3 = 2

fib(4)%3 = ( fib(3)%3 + fib(2)%3 )%3 = (2 + 1)%3 = 0

fib(5)%3 = ( fib(4)%3 + fib(2)%3 )%3 = (0 + 2)%3 = 2

 

따라서

 for (int i = 3; i <= N; i++) 
{
    DP[i] = (DP[i - 2] + DP[i - 1]);
}

에서 구해진 DP[N]을 15746으로 나눈 나머지는

for (int i = 3; i <= N; i++) 
{
    DP[i] = (DP[i - 2] + DP[i - 1])%15746;
}

에서 구해진 DP[N]과 같음.

 

이렇게 하는 이유는 위의 fib(5) 예제에서 봤듯이

계산을 할 때마다 나머지를 구해서 long long형의 범위를 초과하지 않기 위해서

 

 

 

CODE

#include <iostream> 
using namespace std;

int DP[1000001];    //for[1, N]
int N;

int main() 
{
    cin >> N;

    DP[1] = 1;
    DP[2] = 2;

    for (int i = 3; i <= N; i++) 
    {
        DP[i] = (DP[i - 2] + DP[i - 1])%15746; //long long의 범위를 초과하지 않도록
    }

    cout << DP[N] << "\n";

    return 0;
}