[Euler Project 114]

몇 칸짜리 격자를 빨간색이나 검은 색으로 채운다. 이 조건만 있으면 단순히 2의 n승으로 답이 끝난다.

조건은 빨간색은 최소한 연속 3칸 이상 이어져 있어야 한다는 조건이 추가되어 문제가 복잡해진다.

제일 처음 칸 부터 한칸씩 빨간색을 칠할 지, 검은 색을 칠할지를 결정하는 함수를 구성했고, 이 함수를 재귀적으로 불렀다. 어차피 한 칸을 채운 다음에는 남은 몇 칸에 대해 고민하는 것은 똑같으니까. 이전에 빨간색이 아니었다면, 빨간색이 오면 3칸이 무조건 칠해진다. 경우의 수가 줄어든다. 그리고 마지막에 3칸 미만이 남아 있으면 무조건 검정색이 들어갈 수밖에 없다. 뭐 이런 조건들을 함수에서 분기해야 했다.

처음에는 완성된 격자를 다 프린트하는 함수를 만들어서 예시로 주어진 7칸 짜리를 해 봤고, 50을 15로 잘못 읽어서 15칸 짜리도 해 봤다. 그런데, 50칸은 재귀의 깊이가 깊어지기 때문에, 무작정 돌리면 답이 나올 때까지 한~참 걸리는 것 같았다.

그래서 캐시를 생각했다. 전체 50칸을 칠한다고 하자, 지금까지 33칸을 칠했다고 하자. 그럼 남은 건 17칸. 그런데, 마지막 33칸이 검정색인 경우에는 남은 17칸을 칠하는 경우의 수는 17칸짜리를 구성한 경우의 수(이미 계산했을 것이다)와 같다. 그걸 계산하기 위해 재귀를 들어갈 필요 없이 캐시된 경우의 수를 다시 사용하면 된다.

파이썬 코드.