[BOJ] 1904 01타일

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

1904번: 01타일

알고리즘: DP, Math (Fibonacci number)

 

시간복잡도: 1. O(N)

                2. O(p)  (p = 47244, Pisano Period)

 

---

접근:

1. 1, 00 타일로 만들 수 있는 길이가 N인 수열의 모든 가짓수

2. 타일을 붙여서 점점 길이를 확장 (부분문제)

 

-> 1, 2번 조건을 통해 Dynamic으로 접근할 수 있음을 알 수 있다.

 

 

D[N]: 길이가 N인 수열을 만들 수 있는 가짓수 라 두면,

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

로 Dp 배열을 채울 수 있다.

 

D[N-1]: 길이가 N-1인 수열 뒤에 1 타일 붙이기

D[N-2]: 길이가 N-2인 수열 뒤에 00 타일 붙이기

 

 

점화식을 보면 피보나치 수열임을 알 수 있고 이를 통해 시간복잡도를 O(N)에서 더 낮출 수 있다.

 

1. O(logN): 행렬 이용

피보나치 점화식을 행렬로 나타내면 다음과 같이 나타낼 수 있다.

$$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$$

이 n제곱 행렬을 계산하면 우리가 원하는 수열 값을 찾을 수 있다.

허나 단순히 행렬을 곱하면 O(N)의 시간복잡도가 나온다. 

이를 아래의 예시와 같이 계산해주면 O(logN) 만에 값을 구할 수 있다.

 

$$2^{10}=2^{1010_{(2)}}=2^8*2^2$$

$$2^1,\ 2^2,\ 2^4,\ 2^8,\ 2^{16},\ ...$$

이렇게 2의 거듭 제곱꼴로 지수를 구해주면 N번 곱셈을 logN번 곱셈으로 줄여줄 수 있다.

 

(구현은 더 좋은 풀이가 있어서 안했다... 너무 귀찮았다..)

 

 

2. O(p): Pisano Period 이용

https://en.wikipedia.org/wiki/Pisano_period

Pisano period - Wikipedia

피보나치 수를 일정 값(이 문제에선 15746)으로 나눈 나머지는 특정 주기 p를 가진다.

이를 Pisano Period라고 부른다. 자세한건 위키 참조

 

$$피보나치\ 수열을\ 나누는\ 수가\ 10^n꼴이면,\ 주기\ p=15*10^{n-1}이다.$$ 

허나 이 문제는 나누는 수가 10의 거듭제곱 꼴이 아니여서 직접 주기를 계산하였고, 47244라는 값을 구했다.

 

---

1. O(N)

#include <stdio.h>
int N, a[4];
int main(int argc, char* argv[]) {
	scanf("%d",&N);
	
	a[1] = 1;
	a[2] = 2;
	for (int i = 3; i <= N; i++)
	{
		a[3] = (a[1] + a[2])%15746;
		a[1] = a[2];
		a[2] = a[3];
	}
	if (N>2) N = 3;
	printf("%d",a[N]);
	return 0;
}

 

2. O(p)

#include <stdio.h>
int N, a[3];
/*	Calc Pisano Period
	MOD = 15746;
	
	a = 0; b = 1;
	for (int i = 0; i < MOD*MOD; i++)
	{
		c = (a+b)%MOD;
		a = b;
		b = c;
		if (a == 0 && b == 1) break;
	}
	PERIOD = i+1;
*/
int main(int argc, char* argv[]) {
	scanf("%d",&N);
	
	a[0] = 1;
	a[1] = 1;
	N %= 47244;
	
	for (int i = 2; i <= N; i++)
	{
		a[2] = a[0] + a[1];
		if (a[2] >= 15746) a[2]-=15746;
		a[0] = a[1];
		a[1] = a[2];
	}
	printf("%d",a[1]);
	return 0;
}