진흥이는 학교의 임원으로 환경개선을 위해 학교 담장을 여러 가지 색깔로 예쁘게 색칠하는 중이다.

지금 색칠하는 부분을 N개의 구역으로 나누어서 여러 가지 색깔로 각각의 위치를 칠하려고 한다.

이미 다른 색이 일부 칠해져 있고 이번에는 노란색을 칠할 차례이다.

노란색은 어떤 곳이든 여러 곳에 칠할 수 있지만 어떤 한 곳에 칠해지면 그 이웃에 위치한 곳은 같은 색을 칠해서는 안된다.

물론 노란색을 아예 칠하지 않을 수도 있다.

진흥이는 문득 현재 상태에서 노란색을 칠할 수 있는 방법이 몇가지나 있을지 궁금해졌다.

처음부터 한가지씩 세어보다가 너무 많아서 그냥은 셀 수 없다는 것을 알게 되었다.

진흥이를 위해 노란색을 칠할 수 있는 방법이 몇 가지나 있을지 계산하는 프로그램을 작성하라.

색칠하기1 timer 1s memory 64MB

색칠하기1 1s 64MB