[백준/DP] 11726번: 2×n 타일링

2×n 타일링 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

42591

15692

11693

34.706%

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

2

예제 입력 2 복사

9

예제 출력 2 복사

55

 

---

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

/*

	세로로 서있는 마지막 타일에서 뒤쪽에 나올수 있는 것은
	|| or = 임

	N	끝이 세로일 때	|	끝이 가로일 때
	1	1					0	
	2	1					1
	3	2					1
	4	3					2
	5	5					3

	점화식
	v[i - 1].first + v[i - 1].second, v[i-2].first + v[i-2].second

	근데 10007 로 나누는 이유는 오버플로우이기 때문
	처음 문제 이해했을 땐, 모든 경우의 수를 구하고 마지막에 10007로 나눠서 출력하는 건 줄 알았는데
	그러면 10007로 나누는 의미가 없음.
	DP 문제에서 특정한 수(10007) 로 나눠서 출력하라는 의도는, 점화식에 %10007 하라는 의미
	

*/


void dp(vector<pair<int,int>> &v, vector<int> &answer, int N) {
	for (int i = 3; i <= N; i++) {
		v.push_back({ v[i - 1].first + v[i - 1].second, v[i-2].first + v[i-2].second });
		answer.push_back((answer[i - 1] + answer[i - 2])%10007);
	}
}

int main()
{
	int N;
	cin >> N;
	
	vector<pair<int, int>> v;
	vector<int> answer;

	v.push_back({1,0});
	answer.push_back(1%10007);
	v.push_back({ 1,1 });
	answer.push_back(2 % 10007);
	v.push_back({ 2,1 });
	answer.push_back(3 % 10007);

	

	dp(v, answer, N);
	
	cout << answer[N-1] << endl;
	

	return 0;
}