| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2012년 08월 06일 (월) 오후 02시 50분 04초 제 목(Title): Re: [Q] 등대 문제 풀었음.. 기본적인 아이디어는 간단한데 엄밀하게 증명하면 길고 불편해지네요. (특히 등대가 홀수일때랑 축 위에 등대가 여러 개 올라가있을 때) 1. 원점 O를 중심으로 하고 각도 theta인 부채꼴 영역 안에 등대가 n개 있고 등대의 조명각이 theta/n 이라면 등대들로 맞은편 부채꼴 영역 안을 전부 커버 가능하다 2. 무한 평면상에 등대가 n개 있을 경우, 등대들을 반반으로 나누는 직선을 하나 긋고 직선위의 임의의 점을 원점이라고 놓으면 1에 의해서 등대들의 각도를 전부 설정 가능. 1을 증명하는 방법은 기본적으로 / / L2 / / --------------O--------------- / L1 / / / 1.1. L1에 등대들이 있다고 했을 때, L1 영역의 양쪽 어딘가 가장자리에서 theta/n 각도만큼 영역을 떼어냄 해당 영역에는 등대가 한 개만 들어 있어야 함. 그 등대는 떼어낸 부분의 맞은편 영역 (L2의 일부) 을 완전히 덮도록 빛을 조사. 1.2 1.1에 해당하는 영역이 없을 경우에는 O를 L1안의 점으로 적당히 평행이동해서 있도록 만듬. 1.3 1.2가 불가능할 경우 (예: 각 축에 2개 이상의 등대들이 딱 붙어 있을때) L1을 적당히 2개로 분할. 2. 떼어냈든 나눴든 L1, L2의 영역이 줄어들면 남은 부분을 갖고 같은 방식으로 계속 분할. divide and conquer. -- @< //) `//<_ 하얀까마귀 - http://outsider.egloos.com |