[잉여모드] 3m 원안에 가로세로 1cm 사각형을 채워보자.

며칠 전 Google+에서 본 3m 원안에 가로세로 1cm 사각형이 몇가지 들어가는지에 대한 문제(?)
여러가지 재미있는 의견들도 오가고, 많은 풀이가 나왔던...
그리고 며칠이 지난 오늘 약간의 잉여시간을 이용해 내 전공인 코딩을 통해 풀어보았다.
시작은 Google+ 의 한분이 낸 풀이를 이용 좀더 가다듬어서...

기본 알고리즘은 아래와 같다.
1. 반지름이 150cm인 원의 중심점을 원점 0으로 본다.
2. (0,0)부터 사각형을 하나씩 그리기 시작. 1사분면을 채우는 사각형의 수를 구한 후 4를 곱한다.
3. 각 라인(i)을 채우는 사각형의 수는 높이 i, 빗변 150인 직각삼각형의 밑변 길이의 내림값을 구하면 되고, 해당 값은 다음 공식으로 구할 수 있다.

x = ⌊ √( r*r - i*i ) ⌋ 

4. i를 1부터 150까지 증가시키며 각 값을 더해준다.

위 공식의 결과와 소스는 아래 참조.

<script language="Javascript" type="text/javascript">
function countRectFillCircle1(diam){
 var r = diam/2;
 var cnt = 0;

 for(var i=0; i < r; i++){
  var temp = Math.sqrt(r*r - (i+1)*(i+1));
  cnt += parseInt(temp);
 }
 return cnt*4;
}
</script>

여기까지가 기본적인 알고리즘이고...
여기에서 각 줄을 볼때 내림을 하기 전의 소수점 이하 값이 0.5가 넘는다면...
해당 줄을 좌측 혹은 우측으로 밀면 그 줄에 하나의 사각형이 더 들어올 수 있다는 것을 알 수 있다.
그리고 그러한 값을 구하기 위해서는 내림을 하기 전에 0.5를 더해서 내림을 해준다.
위의 줄의 8번째와 10번째 줄을 아래와 같이 바꾸면 OK.
위 공식의 결과와 소스는 아래 참조.

<script language="Javascript" type="text/javascript">
function countRectFillCircle2(diam){
 var r = diam/2;
 var cnt = 0;

 for(var i=0; i < r; i++){
  var temp = Math.sqrt(r*r - (i+1)*(i+1));
  cnt += parseInt(temp+0.5)*2;
 }
 return cnt*2;
}
</script>

하지만 아직 만족스러운 결과는 아니다.
좌우로 밀 수 있다면 위 아래로도 밀수 있다.
하지만 각 줄이 라인을 이루어있는 만큼 위와 같은 방법으로는 안되고,
아마도 통채로 미는 것이 가장 좋은 방법이지 않을까? 

이제 더이상 (0,0) 점에서 시작하는 알고리즘은 안되고, 시작점을 바꿔보자.
반지름(r)에서 시작한다면 당연하겠지만 사각형은 잘려 나갈 것.
그래서 (r-0.5)에서 시작.
물로 최대값을 구하기 위해 위쪽으로 최대로 밀어주는 과정을 한번 거쳐본다.
말로 설명은 이만.... 더이상은 어떻게 설명해야 할지도 모르겠고....  

위 공식의 결과와 소스는 아래 참조.

<script language="Javascript" type="text/javascript">
function countRectFillCircle3(diam){
 var r = diam/2;
 var i = (diam-1)/2;
 var cnt = 0;

 i = parseInt(Math.sqrt(r*r - i*i));
 i = -Math.sqrt(r*r - i*i);
 
 for(;i+1 < r;i++){
  var temp = Math.sqrt(r*r - (i+1)*(i+1));
  cnt += parseInt(temp+0.5)*2;
 }
 return cnt;
}
</script>

더이상은 힘드네요.
일단 이게 정답이라는 것을 증명할 수는 없군요.
최소 이정도 이상은 채울 수 있다는 것을 증명할 수 있는 정도(?).