백준 11726번 2*n 타일링 bfs => 피보나치로 풀기

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

11726번: 2×n 타일링

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

#include <iostream>
#include <queue>
using namespace std;

queue <int> que;

void bfs(int n, int lev)
{
	que.push(lev);
	int now;
	int cnt = 0;
	while (1)
	{
		if (que.empty())
			break;
		now = que.front();
		que.pop();
		if (now == n)
			cnt++;
		if (now + 1 <= n)
			que.push(now + 1);
		if (now + 2 <= n)
			que.push(now + 2);
	}
	cout << cnt % 10007;
}

int main(void)
{
	int n;
	cin >> n;
	bfs(n, 0);

}

처음에 bfs로 푼 코드 

메모리초과가 났다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

메모리 초과는 처음 보네.. 

 

어쨋든 잘 찾아보니 피보나치 수열로 많이 푼 것을 확인하고 그리 하기로 함 

 

#include <iostream>
#include <queue>
using namespace std;

int arr[1001];

int solve(int n)
{
	if (n < 0) return 0;
	if (n == 0) return 1;
	if (arr[n] > 0) return arr[n];
	arr[n] = solve(n - 1) % 10007 + solve(n - 2) % 10007;
	return (arr[n]);
}

int main()
{
	int n;
	cin >> n;
	cout << solve(n) % 10007;
	return 0;
}

참고한 코드 

https://www.acmicpc.net/board/view/39638

글 읽기 - 11726 2*n타일링 문제 질문 드립니다.

피보나치 수열로 푸는 것! n-1 + n-2

근데 10007은 꼭 해야 한다. 안 그러면 너무 큰 수를 판단못함