연결된 점 > 문제은행



실전대비 Level8

1773 : 연결된 점

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 2 회    시도횟수: 21 회   



3×N의 격자형의 각각의 위치에 점이 찍힌 평면을 생각해보자. 그리고 아래와 같이 각 점은 8개의 이웃을 가진다.

 

 

07f1ee470c4ca420b78cf86b19196679_1450337 

위의 평면에서 다음의 조건을 만족하는 다각형을 몇 개를 만들 수 있는지에 대해 알아보고자 한다. 조건은 아래와 같다.

1. 다각형은 3×N의 다각형을 모두 포함해야 한다.
2. 이웃점끼리 직선으로 이을 수 있다.
3. 만들어지는 다각형은 반드시 단순 다각형이어야 한다. 즉, 다각형을 이루는 선끼리 겹치는 점이 없어야 한다.

만들어지게 되는 다각형의 예시는 다음과 같다.

 

07f1ee470c4ca420b78cf86b19196679_1450337 

 

 

N이 주어졌을 때 3 X N의 격자 점 평면에서 위의 조건을 만족시키면서 만들 수 있는 다각형의 숫자를 출력하는 프로그램을 작성하라.




입력은 한 줄로 이뤄지며 1,000,000,000 이하의 양의 정수 N이 입력된다.




입력에 대해 만들 수 있는 다각형의 개수를 1,000,000,000으로 나눈 나머지를 출력한다.



3
8


4
40



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