파이썬으로 그리드 속 만들 수 있는 사각형 개수 구하기

문제 설명

두 값 p와 q가 주어졌다고 가정해 보겠습니다. 점들이 균일한 간격으로 배치된 p행 × q열 그리드에서 만들 수 있는 고유한 정사각형의 개수를 구하는 것이 목표입니다. 답이 매우 커질 수 있으므로, 최종 결과는 10⁹ + 7로 나눈 나머지(mod)를 반환해야 합니다.

여기서 말하는 정사각형은 네 개의 점이 정사각형의 네 꼭짓점을 이루는 경우를 의미합니다. 네 변의 길이는 모두 같아야 하며, 반드시 그리드의 축과 평행할 필요는 없습니다. 즉, 축에 정렬된 사각형뿐만 아니라 기울어진 사각형도 모두 포함됩니다.

예를 들어 입력이 p = 4, q = 4라면 출력은 20이 됩니다.

접근 방법

핵심 아이디어는 각 크기별 경계 상자(bounding box)를 기준으로 사각형을 세는 것입니다. i × i 크기의 경계 상자 하나 안에는 정확히 i개의 서로 다른 정사각형이 존재합니다. 즉, 축에 평행한 사각형 1개와 기울어진 사각형 i − 1개가 함께 들어 있는 셈입니다.

이를 바탕으로 다음 단계를 따르면 됩니다.

• i를 0부터 min(r, c) − 1까지 반복합니다.
• 매번 ans에 (r − i) × (c − i) × i를 더합니다. 여기서 (r − i) × (c − i)는 해당 크기의 경계 상자가 그리드 안에 놓일 수 있는 위치의 수입니다.
• 반복이 끝나면 ans mod (10⁹ + 7)을 반환합니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def solve(self, r, c):
        ans = 0
        for i in range(min(r, c)):
            ans += (r - i) * (c - i) * i
        return ans % (10 ** 9 + 7)

ob = Solution()
print(ob.solve(4, 4))

입력

p = 4
q = 4

출력

20

복잡도 분석

루프가 min(r, c)번만 실행되므로 시간 복잡도는 O(min(r, c))이고, 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다. 덕분에 그리드 크기가 커져도 효율적으로 답을 계산할 수 있습니다.