..

뭔가 우아하게 풀리는 것 같아서 기분이 좋다! d[n] 값을 갱신해주지 않으면 같은 값을 계속 계산하게 되어 시간 초과가 난다. 재귀 호출 시 같은 계산을 또 하지 않도록 처리해주는 것이 중요하다.

숫자를 1, 2, 3과 더하기로만 나타낼 수 있어야 한다. 1은 12는 2 / 1 + 13은 3 / 2 + 1 / 1 + 2 / 1 + 1 + 1 처럼 자신을 포함하여 나타낼 수 있으나 4부터는 자신을 포함하여 나타낼 수 없다. 그러므로 입력이 1, 2, 3일 때 각각 1을 더 더해주어야 한다.

2x1 직사각형과 2x2 직사각형이 들어올 수 있다. 2x2 직사각형이 들어오는 자리에는 1x2 2개, 2x2 1개 총 두 가지의 경우가 있으므로 solve()의 결과에 2를 곱한 값을 더한다.