[BOJ] C/C++ 11727 "2xn 타일링 2"

[BOJ] C/C++ 11727 "2xn 타일링 2" 문제풀이

난이도 : SILVER3

---

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

입력

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

---

출력

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

---

풀이

앞서 풀이했던 11276 2xn 타일링과 거의 같은 문제이다.

omyodevelop.tistory.com/42

11726과 달라진 점은, 2x2 타일이 새로 추가되면서, 오른쪽으로 한 칸 전진하는 방법이 한 가지 늘었다는 것.

또한 2x2 타일이 추가되어 , rec[2] 의 값이 2에서 3으로 바뀌었다.

그냥 완전 동일한 문제라고 봐도 무방해서, 더 풀이할 부분은 없는것같다.

---

소스코드

#include <iostream>
using namespace std;

int main() {
	int rec[1001];
	int N;
	cin >> N;

	//init
	rec[1] = 1;
	rec[2] = 3;

	for (int i = 3;i <= N;i++) {
		rec[i] = (rec[i - 1] + rec[i - 2]*2) % 10007;
	}

	cout << rec[N] << endl;
	return 0;
}

---

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

- 2020.12.24 problem solving