[코딩테스트 연습] 2 x n 타일링

 

문제: https://programmers.co.kr/learn/courses/30/lessons/12900

---

DP 문제입니다.

 

DP[N]: 2 x N개의 타일칸에 놓을 수 있는 방법으로 가정하겠습니다.

 

기저 사례부터 생각해보면,

 

DP[1] = 1, 세로로만 놓을 수 있으므로 1 입니다.

DP[2] = 2, 세로로 두 개, 가로로 두 개 놓을 수 있으므로 2입니다.

 

위 두 개가 기저 사례이고, N > 2 부터는 DP[N]에 대해 다음과 같은 성질이 성립합니다.

 

1. DP[N-1] 방법의 갯수 + 세로로 한 개 놓으면 DP[N]이 됩니다.

2. DP[N-2] 방법의 갯수 + 가로로 두 개 놓으면 DP[N]이 됩니다.

 

위 1, 2번 방법을 모두 더한 게 DP[N]의 가짓 수가 됩니다.

그러므로 DP[N] = DP[N-1] + DP[N-2] (단, N > 2)의 관계가 성립합니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12900.cc