i번째 열에 타일을 채워 넣으려고 할 때, 그 전까지 어떠한 방식으로 타일을 채웠는지에 대한 정보가 모두 필요하지 않습니다.
중요한건, i-1번째 열에서 채워넣었던 타일에 의해, i번째 열을 현재 차지하고 있는 블록의 상태가 어떤지입니다.
i번째 열의 상태는 3칸의 블록이 있거나 없거나의 총 2^3개의 상태만 존재하므로, 이 상태만을 메모이제이션의 인자로 받으면 됩니다.
예를 들어, i번째 열의 현재 타일의 배치와 다음과 같다고 생각해봅시다.
...□□
...□
...□
그렇다면, 이번 열에서는 다음과 같이 타일을 채울 수 있습니다.
...□□
...□■
...□■
...□□
...□■■
...□●●
이런 식으로 모든 경우의 수를 차근차근 따져보시면 됩니다.
isco 5년 전
메모이제이션을 어떻게 해야할지 선뜻 떠오르지 않습니다 ㅠㅠ
고수님들 도와주세요!