동적계획법. [11727]

[1. 문제 설명]

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

---

[2. 풀이 접근]

놓아야 하는 블록은 3가지 유형이 존재한다.

• 1*2 유형의 블록은 항상 같은 블록을 쌍으로 배치할 수 밖에 없다.
• 2*2 유형의 블록은 1*2 유형의 블록을 배치하는 경우와 같은 경우로 볼 수 있다.
• 위 두가지 블록을 배치하려면 적어도 남은 직사각형의 길이가 2 이상이 되어야 한다.

경우의 수를 따지는 문제로, 재귀의 종료조건 달성 시, 한가지 경우를 달성한 것이며,

이 때, 그 경우의 수 1을 반환하도록 한다.

 

부분 문제는 어떤 블록을 배치 시, 남은 직사각형을 어떻게 배치 할 지 결정하면 된다.

• f(n) = f(n-1) + 2*f(n-2)

---

[3. 코드]