정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노 (Polyomino)라고 부른다. N개의 정사각형을 붙여 하나의 폴리오미노를 만들 때 수직방향-단조(vertically monotone)인 폴리오미노를 만들 수 있는 가짓수가 몇 개나 되는지 세고 싶다. 다각형이 수직방향-단조라는 것은, 어떤 수평선도 이 다각형을 두 번 이상 교차하지 않을 때를 말한다.

예를 들어 아래 그림의 (a)는 맨 오른쪽 아래 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아니며 (b)는 두 개의 다각형이 꼭지점만을 맞대고 있으므로 폴리오미노가 아니다. (c)는 폴리오미노이지만 점선과 같은 수평선에 대해 두 번 교차하므로 수직 방향-단조가 아니다. (d) (e) (f)는 모두 7개의 정사각형으로 만들어진 수직방향-단조 폴리오미노이다.

그러면 N개의 정사각형으로 만들 수 있는 수직방향-단조 폴리오미노의 개수를 세는 프로그램을 작성하라.

#1065 upload 158 done 70 how_to_reg 52

폴리오미노 timer 1s memory 128MB

#1065

폴리오미노 1s 128MB