C++로 푸는 직각 이등변 삼각형에 넣을 수 있는 최대 정사각형 개수 구하기

이 문제는 밑변의 길이가 s인 직각 이등변 삼각형(두 변의 길이가 같은 삼각형) 안에 한 변의 길이가 a인 정사각형을 최대 몇 개까지 배치할 수 있는지 구하는 것이 목표입니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력 예시

s = 5, a = 1

출력 결과

10

해설: 삼각형 밑변에 들어갈 수 있는 정사각형의 개수는 밑변 길이를 정사각형 한 변의 길이로 나눈 뒤 1을 빼면 됩니다. 즉, 밑변의 정사각형 개수는 5 ÷ 1 − 1 = 4개입니다.

맨 아래 줄에 4개의 정사각형을 배치하면, 그 위에는 밑변이 (s − a)인 새로운 이등변 삼각형이 만들어집니다. 같은 방법을 반복하면 다음 층에는 3개, 그다음에는 2개를 배치할 수 있고, 마지막으로 꼭짓점에는 정사각형 하나만 놓이게 됩니다. 따라서 전체 개수는 4 + 3 + 2 + 1 = 10개입니다.

접근 방법

• 최대 정사각형 개수를 구하려면 삼각형의 밑변부터 시작해 각 층마다 들어갈 수 있는 정사각형의 개수를 계산합니다.
• 한 층의 정사각형 개수는 밑변 길이 s를 정사각형 한 변 a로 나눈 값에서 1을 뺀 것, 즉 s/a − 1입니다.
• 정사각형을 한 층 배치하고 나면 밑변이 (s − a)인 새로운 이등변 삼각형이 남습니다. 이 삼각형의 다음 층은 바로 아래 층보다 정확히 1개 적은 정사각형을 수용할 수 있으며, 이는 다음과 같이 확인할 수 있습니다.

다음 층의 정사각형 개수 = (s − a)/a − 1 = (s/a − 1) − 1 = s/a − 2 → 바로 아래 층보다 정확히 1개 적습니다.

• 정사각형의 개수는 1이 될 때까지 계속 감소합니다. 따라서 맨 아래 층의 정사각형 개수만 구하면, 1부터 n까지의 자연수 합 공식을 이용해 전체 개수를 손쉽게 구할 수 있습니다.

핵심 공식

1부터 n까지의 합 공식은 다음과 같습니다.

n × (n + 1) / 2

여기서 n = (s/a) − 1이므로, 최종 공식은 다음과 같이 정리됩니다.

((s / a) − 1) × (s / a) / 2

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;

// 최대 정사각형 개수를 계산하는 함수
int Max(int s, int a){
    return ((s / a) - 1) * (s / a) / 2;
}

int main(){
    int s = 5, a = 1;
    cout << "Maximum squares possible are: " << Max(s, a);
    return 0;
}

실행 결과

Maximum squares possible are: 10

이 코드는 반복문 없이 O(1) 시간 복잡도로 답을 구하기 때문에 매우 효율적입니다. 밑변과 정사각형 한 변의 길이만 주어지면 수학 공식 하나로 즉시 결과를 얻을 수 있습니다.