폴리오미노 > 문제은행

본문 바로가기


문제은행

1065 : 폴리오미노

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 28 회    시도횟수: 80 회   



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

 

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

 

e3050b66a1b29a01767400d7560a4131_1449735 

 

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


입력의 첫 번째 줄에는 테스트 케이스의 수 T(1≤T≤50) 가 주어진다. 각 테스트 케이스는 각 줄에 하나의 정수 N(1≤N≤100)이 주어진다.



각 테스트 케이스마다 N개의 정사각형으로 만들 수 있는 수직방향-단조 폴리오미노의 수를 한 줄에 하나씩 출력한다. 단 폴리오미노의 수가 10,000,000 (1천만) 보다 클 경우 1천만으로 나눈 나머지를 출력한다.


[Copy]
5
1
4
2
3
5
[Copy]
1
19
2
6
61


출처 : Algospot


https://algospot.com/judge/problem/read/POLY

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.