C++로 직사각형에 포함되는 정사각형 개수 계산하기

직사각형 속 정사각형 개수 구하기

길이 L과 너비 B(단, L ≥ B)를 가진 직사각형이 주어졌을 때, 이 직사각형 L×B 안에 총 몇 개의 정사각형이 포함될 수 있는지 구하는 것이 목표입니다.

예를 들어 3×2 크기의 직사각형에는 2×2 정사각형 2개와 1×1 정사각형 6개가 들어갑니다.

총 정사각형 개수 = 6 + 2 = 8

규칙 찾기

크기 L×B의 모든 직사각형에는 L×B개의 1×1 정사각형이 존재합니다.
만들 수 있는 가장 큰 정사각형의 크기는 B×B입니다.
L=B=1일 때: 정사각형 수 = 1
L=B=2일 때: 1 + 4 = 5 (2×2 1개, 1×1 4개)
L=B=3일 때: 1 + 4 + 9 = 14 (3×3 1개, 2×2 4개, 1×1 9개)
L=B=4일 때: 1 + 4 + 9 + 16 = 30 (4×4 1개, 3×3 4개, 2×2 9개, 1×1 16개)

B×B 정사각형 안에 포함된 정사각형의 개수는 다음 반복문으로 구할 수 있습니다.

for (i = 1 to B)
    정사각형 수 += i * i;

L이 B보다 클 경우

L > B이면 남는 열만큼 정사각형이 추가로 생깁니다. L = B + 1인 경우(B보다 열이 하나 더 많은 경우), 추가되는 정사각형 수는 다음과 같습니다.

L + (L−1) + … + 3 + 2 + 1 = L(L+1)/2

따라서 추가적인 (L−B)개의 열에서 늘어나는 정사각형 수는 다음과 같습니다.

(L−B) × B × (B+1) / 2

총 정사각형 수 = B×B 내부의 정사각형 수 + (L−B) × B × (B+1) / 2
수열 1 + 4 + 9 + … + B² 부분은 공식 B(B+1)(2B+1)/6으로도 바로 계산할 수 있습니다.

예시

입력 − L=4, B=2

출력 − 직사각형 내 정사각형 개수: 11

설명 − 1×1 정사각형 8개, 2×2 정사각형 3개

입력 − L=3, B=3

출력 − 직사각형 내 정사각형 개수: 14

설명 − 1×1 정사각형 9개, 2×2 정사각형 4개, 3×3 정사각형 1개

알고리즘 접근 방식

직사각형의 크기를 나타내는 정수 length와 breadth를 준비합니다.
함수 numofSquares(int l, int b)는 크기를 전달받아 l×b 직사각형 안의 정사각형 개수를 반환합니다.
가장 큰 정사각형 b×b 내부의 정사각형을 위해 1부터 b까지 반복하면서 각 i² 값을 누적합니다.
l > b인 경우, 추가 열에서 생기는 정사각형 수 (l−b) × b × (b+1) / 2를 누적합에 더합니다.
누적된 squares 값을 최종 결과로 반환합니다.

주의: 항상 length ≥ breadth 조건을 유지해야 합니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int numofSquares(int l, int b){
    int squares = 0;
    // 너비 × 너비 크기의 가장 큰 정사각형 내부의 정사각형 개수
    for(int i = 1; i <= b; i++){
        squares += i * i;
    }
    // 남는 열(l-b)에서 추가되는 정사각형 개수
    squares += (l - b) * b * (b + 1) / 2;
    return squares;
}

int main(){
    int length = 5, breadth = 4; // 항상 length >= breadth 유지
    cout << "정사각형 개수 : " << numofSquares(length, breadth);
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

정사각형 개수 : 40

결과 검증: 4×4 영역의 정사각형 수는 1 + 4 + 9 + 16 = 30개이고, 남은 한 열에서 추가되는 정사각형은 (5−4) × 4 × 5 / 2 = 10개이므로 총 40개로 실행 결과와 일치합니다.