[C++/Python] 백준 11727 - 2xn 타일링 2

문제 링크

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

11727번: 2×n 타일링 2

 

이전 문제와 동일하게 규칙만 찾아내면 구현할 수 있습니다.

 

 

 

 

N이 1일때는 여전히 1가지 방법밖에 없지만 N이 2인경우 2x2 도형이 하나 추가되어 3가지 방법이 생깁니다.

 

N이 3 이후일때는

N-1 의 도형에서 오른쪽에 2x1 세로 도형이 한 개 붙은 형태와

N-2 의 도형에서 오른쪽에 1x2 가로 도형이 두 개 붙은 형태, 2x2 타일이 한 개 붙은 형태로 완성이 됩니다.

 

따라서 N은 dp(N-1) + dp(N-2) * 2 로 구할 수 있습니다.

 

 

구현 코드

 

	#include <iostream>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr);
	using namespace std;
	const int MAX = 1001;
	int d[MAX];
	int dp(int n){
	if(n==1) return 1;
	if(n==2) return 3;
	if(d[n] != 0) return d[n];
	return d[n] = (dp(n-2) * 2 + dp(n-1)) % 10007;
	}
	int main(){
	fastio;
	int n;
	cin >> n;
	cout << dp(n) << endl;
	return 0;
	}

view raw 11727.cpp hosted with ❤ by GitHub

	n = int(input())
	d = []
	d.append(0)
	d.append(1)
	d.append(3)
	for i in range(3,n+1):
	d.append((d[i-1] + d[i-2] * 2) % 10007)
	print(d[n])

view raw 11727.py hosted with ❤ by GitHub