[백준] 1904번: 01타일 풀이 및 해설(C++)

문제 이미지

풀이

명백한 공식을 찾기는 어려워 보인다.

하지만 하위 개수 경우가 상위 개수에 영향을 끼치는 것 같다.

바로 생각이 나지 않을 때는, 한번 나열해 보자.

 

N=2일 때: 11,00 2가지 경우가 있다.

N=3일 때: 001, 100, 111 3가지 경우가 있다

N=4일 때: 0000,0011,1001,1100,1111 5가지 경우가 있다.

N=5일 때: 00001,10000,00100,00111,10011,11001,11100,11111 7가지 경우가 있다.

 

피보나치수열처럼 이전 두 항의 합이 다음 항의 값이 되는 것처럼 보인다. 왜 그럴까?

 

길이가 N인 수열을 만든다고 가정하자.

이전 N-1번째나 N-2번째 수열은 그 사이에 숫자를 삽입하지 않고 뒤에만 숫자를 붙인다고 가정할 수 있다.

이는 N-1번째 수열 뒤에 1을 붙이거나 N-2번째 수열뒤에 00을 붙인 것이다.

따라서 이전 두 항을 더한 피보나치 수열이 답이 된다.

 

그런데 N-2번째 수열 뒤에 11을 붙이는 것은 왜 계산하지 않을까? 아니면 왜 수를 앞에 붙이는 건 생각하지 않을까?

 

K번째 수열은 이미 K개로 표현할 수 있는 모든 수열을 가지고 있다.

따라서 숫자를 어디에 붙이든 상관이 없으며, N-1번째 수열에는 이미 1이 N-1개인 수열이 있을 것이다.

따라서 중복을 막기 위해서는 전 항 2개만 합하는 피보나치수열을 구하면 된다.

 

그런데 그냥 피보나치 수열을 구하면 정수 범위를 초과하니 항상 15746으로 나누어 구한다.

 

 

해답 코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    int n;
    cin>>n;
    int arr[n+1];
    arr[1]=1;
    arr[2]=2;
    for(int i=3; i<n+1; i++){
        arr[i]=(arr[i-1]+arr[i-2])%15746;
    }
    cout<<arr[n];
    return 0;
}