BaekJoon(1904)::01타일

문제

1904번: 01타일

문제 파악

이 문제는 결국 00타일 1타일 두개로 N길이의 타일을 만들수 있는 가지수를 구하는 문제이다.

그림으로 그려봐도 알 수 있는 것처럼 결국 N-2 타일에 00을 붙이냐 N-1타일에 1을 붙이냐의 차이의 문제가 될것같다

$$f(n) = f(n-1) + f(n-2)$$

문제 풀이

문제 파악과정에서 알게 된 수식을 보면 피보나치 수열과 같음을 알 수 있다.

피보나치 수열의 단점은 시간이 오래 걸릴수 있다는 점이다. 이 점을 해결하기 위해 dp를 사용할 예정이다.

#include<iostream>
using namespace std;
long dp[1000001];

int main() {
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;

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

	int n;
	cin >> n;
    
	cout << dp[n] << endl;

	return 0;
}​

주의 할 점

문제에서 15746으로 나눈 나머지라는 점을 놓치면 문제 해결에 많은 문제가 될 것이다.