분할 정복법으로 타일 채우기

$1 \times n$ 격자판을 $1 \times 1$, $1 \times 2$, $1 \times 3$ 타일로 빈틈없이 채우는 서로 다른 방법의 수를 분할 정복법으로 구하시오. 타일을 놓는 순서는 구별하지 않고, 왼쪽부터 어떤 타일이 놓였는지가 다르면 서로 다른 방법이다.

첫째 줄에 격자판의 길이 $n$이 주어진다. ($1 \le n \le 20$)

격자판을 채우는 방법의 수를 한 줄에 출력한다.