문제 개요
직각 이등변 삼각형은 두 변의 길이가 같은 이등변 삼각형 중에서 높이(그림의 ag)와 밑변(그림의 dg)이 서로 수직을 이루는 삼각형입니다. 이 문제의 목표는 한 변의 길이가 2인 정사각형이 직각 이등변 삼각형 안에 최대 몇 개까지 들어갈 수 있는지 구하는 것입니다. 밑변과 높이(두 값이 동일함)가 입력으로 주어지며, 들어갈 수 있는 정사각형의 개수가 출력됩니다.
아래 그림을 참고하면 문제를 더 쉽게 이해할 수 있습니다.
핵심 아이디어
높이 ag와 밑변 gd를 가진 삼각형에는 한 변이 2인 정사각형 3개가 들어갑니다. 여기서 중요한 점은 모서리 끝부분의 삼각형 aib와 cde에는 어떤 정사각형도 들어갈 수 없다는 사실입니다. 따라서 항상 양쪽 끝에 대해 각각 2단위씩, 총 2단위의 여분 길이를 먼저 제외해야 합니다. 그다음 남은 밑변 gd(또는 높이 ag)를 2로 나누면 한 줄에 배치할 수 있는 정사각형의 개수를 셀 수 있으며, 높이 방향도 동일한 방식으로 계산합니다.
while(base > 2)
squares += (base-2)/2
base = base-2
등차수열 공식 Ap = b*(b+1)/2 활용… 단, 새로운 b = b-2
예제로 이해하기
입력 − 밑변: 12
출력 − 정사각형 개수: 15
풀이 과정
base 12>2, squares 10/2=5, 새 base 12-2=10
base 10>2, squares 8/2=4, 새 base 10-2=8
base 8>2, squares 6/2=3, 새 base 8-2=6
base 6>2, squares 4/2=2, 새 base 6-2=4
base 4>2, squares 2/2=1, 새 base 4-2=2
base 2>2 X → 총 정사각형 개수 = 5+4+3+2+1 = 15
입력 − 5
출력 − 정사각형 개수: 1
풀이 과정
base 5>2, squares 3/2=1, 새 base 5-2=3
base 3>2, squares 1/2=0, 새 base 3-2=1
base 1>2 X → 총 정사각형 개수 = 1
알고리즘 접근 방식
정수형 변수 base에 삼각형의 밑변 길이를 저장합니다.
함수 numofSquares(int b)는 밑변이 b인 삼각형에 들어갈 수 있는 정사각형의 개수를 계산합니다.
먼저 b = b - 2를 수행해 모서리 끝부분의 여분 공간을 제거합니다.
공식에 따라 b = floor(b / 2)로 만들면, 새로운 b에 대해 b*(b+1)/2개의 정사각형(한 변의 길이 2)이 들어갑니다.
계산된 결과를 정사각형의 개수로 반환합니다.
C 코드 예제
#include <stdio.h>
#include <math.h>
int numofSquares(int b){
// 항상 필요한 여분 부분 제거
b = (b - 2);
// 각 정사각형의 밑변 길이가 2이므로
b = floor(b / 2);
return b * (b + 1)/2;
}
int main(){
int base = 8;
printf("들어갈 수 있는 최대 정사각형 개수 : %d",numofSquares(base));
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
들어갈 수 있는 최대 정사각형 개수 : 6