문제 이해하기
정삼각형의 한 변의 길이가 주어졌을 때, 삼각형 내부에 만들 수 있는 서로 다른 직사각형의 개수를 구하는 것이 목표입니다. 단, 직사각형의 수평 방향 변은 정삼각형의 밑변과 평행해야 하며, 직사각형의 네 꼭짓점은 모두 삼각형을 구성하는 격자점 위에 위치해야 합니다.
예제를 통해 문제를 자세히 살펴보겠습니다.
예제
입력 − sides = 3
출력 − 정삼각형에 내접하는 서로 다른 직사각형의 개수 − 1
설명 − 변의 길이가 3일 때 조건을 만족하는 직사각형은 하나만 존재합니다.
입력 − sides = 10
출력 − 정삼각형에 내접하는 서로 다른 직사각형의 개수 − 200
접근 방식
그림에서 확인할 수 있듯이, 직사각형의 수평 변은 한 칸씩 건너뛴 레벨(level), 즉 교차하는 층의 점들 사이에만 존재할 수 있습니다.
따라서 각 직사각형의 윗변과 아랫변이 놓일 수 있는 점의 개수는 레벨 0-1, 레벨 1-2, ... , 레벨 n-(n+1) 형태로 차례대로 계산할 수 있습니다.
여기서 주의할 점은 sides의 홀짝 여부입니다. 변의 길이가 홀수인지 짝수인지에 따라 각 레벨에서 선택 가능한 점의 개수가 달라지므로, 두 경우를 구분하여 계산해야 합니다.
알고리즘 단계
- 변의 길이(sides)를 정수 변수로 입력받아 이후 처리를 위해 함수에 전달합니다.
- 임시 변수로 count, temp, check를 선언합니다.
- sides가 홀수인 경우, i를 sides-2부터 시작하여 i가 1 이상인 동안 FOR 반복문을 실행합니다.
- 반복문 안에서 i가 홀수(i & 1)이면 temp를 (sides - i) / 2로, check를 (i * (i + 1)) / 2로 설정한 뒤 count에 check * temp를 더하고, i가 짝수이면 temp를 ((sides - 1) - i) / 2로, check를 (i * (i + 1)) / 2로 설정한 뒤 동일하게 누적합니다.
- sides가 짝수인 경우에도 마찬가지로 i를 sides-2부터 1까지 반복문을 실행합니다.
- 반복문 안에서 i가 홀수이면 temp를 ((sides - 1) - i) / 2로, check를 (i * (i + 1)) / 2로 설정하여 count에 누적하고, i가 짝수이면 temp를 (sides - i) / 2로, check를 (i * (i + 1)) / 2로 설정하여 count에 누적합니다.
- 반복이 끝나면 최종적으로 count를 반환합니다.
- 결과를 화면에 출력합니다.
예제 코드
#include <iostream>
using namespace std;
int rec_inside_equi(int sides){
int count = 0, temp, check;
if(sides%2 != 0){
for(int i = sides - 2; i >= 1; i--){
if (i & 1){
temp = (sides - i) / 2;
check = (i * (i + 1)) / 2;
count += check * temp;
}
else{
temp = ((sides - 1) - i) / 2;
check = (i * (i + 1)) / 2;
count += check * temp;
}
}
}
else{
for(int i = sides - 2; i >= 1; i--){
if (i & 1){
temp = ((sides - 1) - i) / 2;
check = (i * (i + 1)) / 2;
count += check * temp;
}
else{
temp = (sides - i) / 2;
check = (i * (i + 1)) / 2;
count += check * temp;
}
}
}
return count;
}
int main(){
int sides = 4;
cout<<"Count of distinct rectangles inscribed in an equilateral triangle are: "<<rec_inside_equi(sides);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Count of distinct rectangles inscribed in an equilateral triangle are: 4