Creative Commons License

Software Dev

프로그래밍기본
객체지향
프로젝트관리
알고리즘
데이타베이스

소프트웨어 개발에 필수적이고 필요한 주제에 대한 강의 및 공유

.

알고리즘

주어진 문제를 효과적으로 해결하기 위한 문제해결논리에 대해 다룹니다

[문제] 바닥을 빈틈없이 매울 수 있는 정다각형의 종류

작성자 : 박종명
최초 작성일 : 2010-03-23 (화요일)
최종 수정일 : 2010-03-23 (화요일)
조회 수 : 10459

또 문제입니다 ^^; 계속 문제네요 ㅎㅎ

----------------------------------------------------------------------------------------------------------

문제
가로, 세로 1m인 정사각형 판자 위에 한 변의 길이가 10cm인 같은 종류의 정다각형을 겹치지 않게 놓아서 정사각형 판자를 빈틈없이 덮으려고 한다. 정다각형의 일부가 판자 밖으로 나가는 것을 허용하고 사용하는 정다각형의 개수는 제한이 없다고 할 때, 판자를 빈틈없이 덮는 것이 가능한 정다각형의 종류는 몇 가지인가? 예를 들어 아래 그림과 같이 정오각형을 이어 붙인 경우에는 사이에 빈틈이 생기므로 정오각형은 답이 될 수 없다.

                                                                                                 - 출처: 한국정보올림피아드 기출 -

 

어디선가 많이 들어봄직한 문제이다

벌들이 왜 벌집을 정육각형으로 만드는가?
왜 바닥의 타일은 정XX각형 인가?


삼각형 그리고 정 다각형의 성질을 이용한 꽤나 많이 응용되던 문제인 것 같다

문제를 다시 보면,
정사격형 판자가 있고, 그 위에 정다각형을 겹치지 않고 이어 붙였을 때 밑에 깔린 (정사격형)판자가 보이지 않도록
빈틈없이 덮고자 한다. 다만 빈팀은 없되, 덮고 있는 정다각형이 밖으로 삐져 나가는 것은 허용한다.
그리고 정다각형 갯수는 상관 없다. 이때 가능한 정다각형의 종류는 몇 가지?
참고로 정오각형은 겹치지 않고 이어 붙였을 때 중간에 빈틈이 있어서 실격!!!

풀어 쓴다고 썼는데도 뭔가 복잡해 보인다. 그림을 보자

왼쪽의 정사각형을 오른쪽의 다각형 중 하나를 이용해서 빈 틈 없이 이어 붙일 수 있는 게 무엇인가?

정삼각형, 정사각형, 정오각형, 정육각형,..... 정 이백각형....

정 다각형의 종류는 무수히 많다

이것을 일일이 머리속에 대략 그림으로 때려 잡아 그려 볼 수는 없는 것이다

문제를 풀기 위한 핵심은 다음과 같다
1) 정 다각형을 이어 붙인다
2) 겹치지 않아야 한다
3) 빈틈이 있어서도 안된다

문제의 핵심은, 정 다각형을 겹치지 않고 이어 붙였을 때 중간에 빈틈이 없으면 되는 것이다

즉 특정 꼭지점을 기준으로 정 다각형을 삥~ 둘렀을 때 다각형의 내각의 합이 딱 360도가 되어야 한다는 것이다
꼭지점을 둘러산 정다각형들의 내각의 합이 360도 보다 작으면 중간에 빈틈이 생기는 것이며
360도 보다 크면 다각형들이 겹쳐지게 되는 것이다


정삼각형을 예로 들어 보면, 아래 그림처럼 중간 꼭지점을 기준으로 둘러싼 정삼각형들 사이에 빈 틈이 없다

삼각형의 내각의 합은 180도 이다. 그러므로 정 삼각형의 한 내각의 크기는 60도가 된다
60 * 6 = 360 도 정확히 떨어진다. 즉 정삼각형은 조건에 만족하게 되는 것이다

그리고 이러한 삼각형의 성질을 이용하여 다각형의 내각의 합, 한 내각의 크기를 구할 수 있는데
공식은 다음과 같다

정 n 각형의 한 내각의 크기 =    

(이 공식이 성립하는 근거는 수학교과서나 인터넷 자료를 찾아 보길 바란다)


따라서 정 다각형의 한 내각의 크기를 알아 낸 뒤 그 내각의 합이 360도가 되는지 알아보면 되는 것이다
360 를 한 내각의 크기로 나누었을 때 나누어 떨어지면 되는 것이다

각각의 정 다각형을 360 / 내각의 크기 해 보면,

정삼각형: 360 / 60   = 6  (나누어 떨어짐)
정사각형: 360 / 90   = 4
정오각형: 360 / 108 =  3.3333...
정육각형:  360 / 120 = 3

정칠각형: 이후로는 볼 것도 없다. 한 내각의 크기가 120도 보다 크기 때문에 세 조각을 합치면 360도가 넘는다

결과적으로 적합한 정 다각형의 수는 총 3가지(정삼각형, 정사각형, 정육각형)이 된다

 

함수로 만들 필요가 있겠나.. 만은

패턴을 유지하기 위해 함수화 시켜 보기로 하자

함수 설명: 차수 N인 정 N 다각형이 겹치지 않고 이어 붙였을 때 공백이 생기는치 체크
입력 매개변수: 차수 N
출력 매개변수: 공백없이 이어붙일 수 있는지 없는지에 대한 참/거짓

함수 정의>>
static bool Is360Degree(int angleDegree)
{
      double angle = (double)180 * (angleDegree - 2) / angleDegree; //한 내각의 크기

      return ((360 % angle) == 0) ? true : false; //360을 내각으로 나눈 결과 0이면 true , 아니면 false
}

함수 사용>>
static void Main(string[] args)
{
      bool result = Is360Degree(6); //정 6각형 체크하기
      Console.WriteLine(result);
}

이름
비밀번호
홈페이지
TA <- 왼쪽의 문자를 오른쪽 박스에 똑같이 입력해 주세요