[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 로 구할 수 있습니다.

 

 

구현 코드