By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:
Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
3x2 그리드에서 볼 수 있는 사각형을 주의깊게 세어 보면 18개가 나온다:
정확하게 2백만 개 사각형이 있는 그리드는 없지만, 2백만에 가장 가까운 그리드를 구하시오.
--------------------------------------------------------------------------
가로 세로로 나눠 생각해보면, 크기 3인 면(3x1 그리드)에 크기 1의 사각형은 3개, 크기 2의 사각형은 2개, 크기 3의 사각형은 1개 들어간다. 즉, (크기-사각형 크기+1)의 합계가 된다. 여기에 세로 길이를 고려하여 갯수를 구하면(가로x세로) 전체 사각형 갯수가 나온다.
이 문제에서는 2백만에 가장 가까운 그리드를 요구했는데, 2백만 보다 큰 지 작은 지 정확히 나오지 않아 두 경우를 모두 고려해야 했다.
그리고, 가로, 세로 크기에 한계를 정하지 않은 상태여서 그 부분을 미리 유추해야 할 필요가 있다. 가만히 보면 가로 합계x세로 합계가 형태이므로, (x(x+1)/2)*(y(y+1)/2)의 공식이 나오게 된다. 즉, x2*y2이므로 가로 세로가 100일 때 천만 이상의 사각형이 나오게 되므로, 여유를 주고 반복문을 통해 2백만에 근접한 값을 구하게 했다.
공식을 생각하기 전에 사각형 갯수를 구하는 반복문을 만들어서 그대로 썼는데, 간단한 공식으로 구할 것을 사각형 크기별로 합계를 모두 구하게 해서, 실행 속도를 손해보게 된 것 같다.