사각 격자 안에 포함된 사각형 개수 세기
가로 세로 인 격자에서 각 크기의 사각형이 몇 개씩 들어가는지 생각해보자. 크기(가로세로)가 인 사각형은 생각할 것도 없이 개가 들어간다. 크기가 인 사각형은 가로 방향으로는 개, 세로 방향으로는 개가 들어갈 수 있으므로 개수는 이 될 것이다.
가로 크기를 로 고정시킨 상태에서 세로 크기를 부터 까지 바꿔가며 격자에 포함될 수 있는 사각형의 개수를 구하면 다음과 같다.
격자에 포함될 수 있는 사각형 중 가로가 1인 사각형의 개수를 이라 하면 다음과 같이 나타낼 수 있다.
가로가 인 사각형의 개수 는 다음과 같이 나타날 수 있다.
따라서 격자에 들어갈 수 있는 사각형 갯수 은 다음과 같이 나타낼 수 있다.
이 공식을 이용해 격자에 들어갈 수 있는 사각형의 개수를 구하는 함수는 다음과 같이 작성할 수 있다.
(defn rect-cnt [m n]
(/ (* m (inc m) n (inc n)) 4))
격자에 포함될 수 있는 사각형의 개수가 2백만 개에 가까운 격자 크기를 구해야 하므로 다음과 같이 주어진 수와 2백만의 차(절대값)를 구하는 함수도 작성해 놓으면 도움이 될 것이다.
(defn delta [n]
(Math/abs (- 2000000 n)))
이제 격자 크기를 바꿔가며 격자에 포함될 수 있는 사각형의 개수가 2백만에 가장 가까운 경우를 찾으면 된다. 격자 한 변의 최대 크기를 100 이하로 구해보면 될 것 같다. 그래봤자 루프를 1만 번만 돌면 된다.
(defn solve []
(let [MAX 100]
(->> (for [x (range 1 MAX)
y (range 1 MAX)
:let [cnt (rect-cnt x y)]]
[x y cnt (delta cnt)])
(apply min-key last)
((fn [[x y _ _]] (* x y))))))
실행 결과는 다음과 같다. 빠른 시간에 답을 구한다.
p085=> (time (solve)) "Elapsed time: 91.497031 msecs" 2??2