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

문제 링크

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

11726번: 2×n 타일링

 

 

 

 

위 그림으로 봤을 때

 

N이 1일때는 방법이 한가지, 2일때는 두가지의 방법이 있습니다.

 

N이 3 이후일때는

N-2 의 도형에서 가로 두 개의 도형이 오른쪽에 붙은 형태와

N-1 의 도형에서 세로 한 개의 도형이 오른쪽에 붙은 형태로 완성이 됩니다.

 

이를 통해 N은 dp(N-1) + dp(N-2) 로 구할 수 있다는걸 알 수 있습니다.

 

구현 코드