동적 계획법으로 타일 채우기

$1 \times n$ 격자판을 $1 \times 1$, $1 \times 2$, $1 \times 3$ 타일로 빈틈없이 채우는 서로 다른 방법의 수를 동적 계획법으로 구하시오. 한 번 구한 부분 문제의 답은 다시 계산하지 않는다.

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

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