[C++/알고리즘] 백준 11727 (2xn 타일링2)

 

 

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

11727번: 2×n 타일링 2

이 문제는 다이나믹 프로그래밍 방식으로 풀면 되는 문제로

 

제일 마지막에 올 타일이

2x2 의 타일과 1x2 타일을 가로로 두 개 두는 경우, 그리고 2x1의 타일을 세로로 한 개 두는 경우.

이렇게 세 가지 방법이 있다고 가정하고 풀면 된다.

 

 

재귀 호출 방식으로

2x1와 2x2 타일이 제일 마지막에 위치하는 경우는 solution(n-2)를 두 번 호출 하고

1x2 타일이 제일 마지막에 위치하는 경우 solution(n-1)을 더해줬다. 

 

 

#include <iostream>

using namespace std;
int d[1001];

int solution(int n)
{
	if (d[n] > 0)return d[n];
	if (n == 1 || n == 0) return 1;

	d[n] = (2 * solution(n - 2) + solution(n - 1)) % 10007;

	return d[n];
}

int main()
{
	int n;
	cin >> n;
	cout << solution(n) << endl;
}

 

시간 초과 발생

처음에 저장하는 부분을 따로 두지 않아서 return d[n]을 해주지 않고 제출 했더니 시간 초과가 떴다.