오일러 프로젝트 85

오일러 프로젝트 85 번 문제는 사각격자내에 그릴 수 있는 사각형의 수와 관련한 문제이다. 80번대 문제 중에서도 낮은 난이도를 보이는 “잠깐 쉬어가는 문제”같은 느낌이다.

3 X 2의 크기의 격자를 주의깊게 조사해보면, 그 안에는 아래 그림과 같이 18개의 사각형이 포함됨을 알 수 있습니다.

이런식으로 세었을 때 사각형을 정확히 2백만개 포함하는 격자는 존재하지 않는다고 합니다. 2백만에 가장 근접한 개수의 사각형을 포함하는 격자를 찾고, 그 넓이를 구해보세요.

(http://euler.synap.co.kr/prob_detail.php?id=85)

접근

우선 높이를 1로 고정하고 가로폭이 A인 격자에서 사각형을 만들 수 있는 경우를 생각해보자.

  1. 폭이 1인 사각형을 A개 만들 수 있다.
  2. 폭이 2인 사각형은 A-1개 만들 수 있다.
  3. 폭이 3인 사각형은 (A-2)개 만들 수 있다.
  4. 같은 식으로 폭이 B인 사각형은 (A + 1 – B)개 만들 수 있다.

폭 A인 경우에 만들 수 있는 사각형 B의 범위는 1 \ge B \ge A 이며, 각각의 사각형의 수는 A, (A-1), … , 3, 2, 1개가 된다. 즉 폭이 A인 경우 높이 1인 사각형은 1+2+3+…+A 개를 만들 수 있다. 똑같은 원리로 폭이 1이면서 높이가 C인 격자에서 만들 수 있는 사각형의 개수도 1 + 2 + 3 + … + C 개 이다. 따라서 A x C의 격자에서 만들 수 있는 모든 사각형의 개수는 \frac{A(A+1)}{2} \times \frac{C(C+1)}{2} 개가 된다. 이 값은 A나 C가 커지면 당연히 같이 커진다.

이 값이 200만에 근접해야 한다. 만약 이 값을 200만으로 두고 A, C 둘 중 하나를 1로 고정하면 나머지 한쪽의 최대 길이는 2000까지 될 수 있다. (A(A+1) = 4000000) 따라서 폭과 너비가 1~2000 범위일 때 만들 수 있는 사각형의 수가 200만에 가장 근접할 때를 찾으면 된다. 전체 케이스가 약 4백만 가지인데, 폭과 높이 조합에서 순서는 중요하지 않으므로 그 절반만 보면 된다. 케이스 범위가 크지 않으므로 전량을 검사해도 0.01초 내외로 계산된다.

func possibleNumberOfRects(width: Int, height: Int) -> Int {
  return width * (width + 1) * height * (height + 1) / 4
}

let limit = 200_0000
var (area, minDiff) = (0, limit)
for y in 1...2000 {
  for x in y...2000 {
    if case let diff = abs(limit - possibleNumberOfRects(width: x, height: y)),
       minDiff > diff {
      (area, minDiff) = (x*y, diff)
    }
  }
}
print(area)