프로젝트 오일러 147번

In a\(3 \times 2\) cross-hatched grid, a total of \(37\) different rectangles could be situated withing that grid as indicated in the sketch.

There are \(5\) grids smaller than \(3 \times 2\), vertical and horizontal dimensions being important, i.e. \(1 \times 1\), \(2 \times 1\), \(3 \times 1\), \(1 \times 2\) and \(2 \times 2\). If each of them is cross-hatched, the following number of different rectangles could be situated within those smaller grids:

\(1 \times 1: \; 1\)

\(2 \times 1: \; 4\)

\(3 \times 1: \; 8\)

\(1 \times 2: \; 4\)

\(2 \times 2: \; 18\)

Adding those to the \(37\) of the \(3 \times 2\) grid, a total of \(72\) different rectangles could be situated within \(3 \times 2\) and smaller grids.

How many different rectangles could be situated within \(47 \times 43\) and smaller grids?

---

위 그림에서 처럼 \(3 \times 2\) 십자 형상의 격자에서는 \(37\) 개의 직사각형을 찾을 수 있다.  \(3 \times 2\) 보다 크기가 작은 격자는 \(1 \times 1\), \(2 \times 1\), \(3 \times 1\), \(1 \times 2\), \(2 \times 2\) 의 \(5\) 개가 있으며 이들 각각에서는 다음과 같은 수의 직사각형을 찾을 수 있다.

\(1 \times 1: \; 1\)

\(2 \times 1: \; 4\)

\(3 \times 1: \; 8\)

\(1 \times 2: \; 4\)

\(2 \times 2: \; 18\)

따라서 \(3 \times 2\) 모양의 격자와 그 보다 크기가 작은 격자에서 찾을 수 있는 직사각형의 총 개수는 \(72\) 개가 된다.

그렇다면 \(47 \times 43\) 모양의 격자와 그 보다 크기가 작은 격자에서 찾을 수 있는 직사각형은 총 몇 개일까? 

사실 가로나 세로줄로만 이루어진 (대각선을 포함하지 않는) 직사각형의 개수를 찾는 것은 어렵지 않다. 고등학교 수학 시간에 늘 풀던 문제이기 때문이다. \(m \times n\) 크기의 격자에서 찾을 수 있는 대각선을 포함하지 않는 직사각형의 개수는 \[{_{m+1}{\rm C}_2} \times {_{n+1}{\rm C}_2} = \dfrac{m(m+1)}{2} \times \dfrac{n(n+1)}{2}\] 이 된다.  

이 문제의 핵심은 대각선으로 이루어진 직사각형의 개수를 세는 것에 있다. 이를 위해서 먼저 작은 크기에서 큰 크기의 순으로 격자들의 직사각형 수를 세어 나가고, \(m \times n\) (단, \(m \le n\)) 크기의 격자에서 대각선으로 이루어진 직사각형의 개수를 세기 위해서는 \(m \times (n-1)\) 에 \(1 \times m\) 격자를 붙여나가는 방식으로 직사각형의 개수를 세어 나갈 것이다. 예를 들어, \(3 \times 5\) 모양의 격자에서 대각선으로만 이루어진 직사각형의 개수를 찾기 위해서는 일단 \(3 \times 4\) 모양의 격자에서 찾은 대각선으로만 이루어진 직사각형의 개수에다가 \(1 \times 3\) 모양의 격자를 붙여 새롭게 만들어지는 대각선으로만 이루어진 직사각형의 개수를 더하는 방식으로 찾아 나가는 것이다. 다음은 이 과정을 보여주는 영상이다.

아래의 point 함수는 위 영상에서 설명한 새로운 직사각형의 꼭짓점이 되는 포인트들을 구해주는 함수이다.

def point(n):
    result = [[0.5, 0.5]]
    for i in range(1, n):
        result.append([i, 0])
        result.append([i + 0.5, 0.5])
    return result

아래의 addition 함수는 하나의 포인트를 꼭짓점으로 하여 새롭게 생겨나는 직사각형의 개수를 구해주는 함수이다.

def addition(point, m, n):
    y = point[1]
    xh = point[0]
    sum = 0
    while y < n - 0.5 and xh < m:
        xl = point[0]
        y += 0.5
        xh += 0.5
        while xl > 0:
            xl -= 0.5
            if point[1] + xh - xl <= n:
                sum += 1
            else:
                break
    return sum

 

이렇게 하여 루프를 하나는 1~47까지, 하나는 1~43까지 돌려서 직사각형의 개수를 얻어내면 된다.

이때, dictionary를 이용하여 각 크기의 격자에 대한 직사각형의 개수를 저장하여 필요할 때 사용하는 것이 편리하며, 영상에서도 언급했지만 \(m \times n\) 이나 \(n \times m\) 모양의 격자는 같은 수의 직사각형을 포함하고 있으므로 dictionary를 업데이트 할 땐, 항상 두 개를 모두 업데이트 해 주는 방향으로 하는 것이 좋을 듯 싶다. 또한 \(1 \times n\) 격자의 경우 대각선으로만 이루어진 직사각형의 개수가 \(n-1\) 개 있으므로 이 부분은 별다른 계산없이 dictionary에 추가하고 시작해야 한다.

이런식으로 하면 수초 내에 답을 얻어낼 수 있다. 나의 똥컴에서 약 6초 정도 소요되는 것을 확인하였다.

한 가지 추가할 내용 !!!

아직 이해하지 못한 내용이기는 한데, \(m \times n\) (단 \(m \ge n\)) 모양의 격자에서 얻을 수 있는 대각선으로만 이루어진 직사각형의 개수는 \[\dfrac{n \{ (2m-n) \left ( 4n^2 -1 \right ) -3 \}}{6}\;\; (m \ge n)\] 이라고 한다. 늙어가는 이 머리로는 아직 이해가 가지 않는 공식인데, 실제 이걸 이용해서 답을 구해보면 1초도 걸리지 않아 답이 나오는 것을 볼 수 있다. 혹시 위 공식을 이해하신 분이 있다면 도움의 손길을 좀 주시길 ....