C++로 체스판 속 정사각형 개수 구하는 프로그램

문제 소개

이번 문제에서는 체스판의 크기가 주어졌을 때, 그 체스판 안에 존재하는 모든 정사각형의 개수를 구하는 프로그램을 C++로 작성합니다.

문제 설명

단순히 눈에 보이는 칸만 세는 것이 아니라, 체스판 내부에 만들 수 있는 모든 크기의 정사각형 조합을 계산해야 합니다. 즉, 한 변의 길이가 1×1, 2×2, 3×3 … n×n인 정사각형을 모두 찾아 더해야 합니다.

예시로 이해하기

입력: n = 4

출력: 30

크기 1×1인 정사각형 → 16개
크기 2×2인 정사각형 → 9개
크기 3×3인 정사각형 → 4개
크기 4×4인 정사각형 → 1개
정사각형의 총 개수 = 16 + 9 + 4 + 1 = 30

4×4 체스판이라면 1칸짜리 정사각형 16개뿐만 아니라, 인접한 칸들을 묶어 만든 2×2, 3×3, 4×4 정사각형까지 모두 포함해 총 30개가 됩니다.

풀이 접근법

n×n 격자에서 각 크기별 정사각형의 개수를 살펴보면 다음과 같은 패턴을 발견할 수 있습니다.

sum(1) = 1
sum(2) = 1 + 4 = 5
sum(3) = 1 + 4 + 9 = 14
sum(4) = 1 + 4 + 9 + 16 = 30

즉, k×k 체스판에는 k² 개의 k×k 정사각형이 존재하므로, 전체 개수는 1부터 n까지 자연수의 제곱합과 같습니다. 이를 일반화하면 다음 공식으로 나타낼 수 있습니다.

sum = 1² + 2² + 3² + 4² + … + n²
sum = (n × (n + 1) × (2n + 1)) / 6

이 공식은 잘 알려진 '제곱수의 합' 공식으로, 반복문 없이 단 한 번의 연산으로 답을 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;
int calcSquaresCount(int n){
    int squareCount = ((n * (n+1) * (2*n + 1)) / 6);
    return squareCount;
}
int main() {
    int n = 6;
    cout<<"The total number of squares of size "<<n<<"X"<<n<<" is "<<calcSquaresCount(n);
}

실행 결과

The total number of squares of size 6X6 is 91

위 코드는 제곱수의 합 공식을 활용해 시간 복잡도 O(1)로 결과를 계산합니다. n이 커져도 성능 저하 없이 즉시 답을 구할 수 있다는 점에서, 단순 반복문 방식보다 훨씬 효율적인 해결책입니다.