티스토리 뷰

Coding Test/백준

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

Junchoi 2020. 7. 21. 14:00

문제 링크

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

 

 

 

 

위 그림으로 봤을 때

 

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

 

N이 3 이후일때는

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

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

 

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

 

구현 코드

 

 

'Coding Test > 백준' 카테고리의 다른 글

[C++/Python] 백준 9095 - 1, 2, 3 더하기  (0) 2020.07.23
[C++/Python] 백준 11727 - 2xn 타일링 2  (0) 2020.07.22
[C++/Python] 백준 1463 - 1로 만들기  (0) 2020.07.20
[C++/Python] 백준 13015 - 별찍기 - 23  (0) 2020.07.17
[C++/Python] 백준 10997 - 별찍기 - 22  (0) 2020.07.16