높이(height)와 너비(width)가 주어진 직사각형이 있고, 이 직사각형은 왼쪽 아래 모서리가 원점 (0, 0)에 위치한 2차원 좌표계 위에 놓여 있습니다. 이때 목표는 다음 조건을 모두 만족하는 마름모가 직사각형 내부에 몇 개나 만들어질 수 있는지 세는 것입니다.
- 마름모의 넓이는 0보다 커야 합니다.
- 마름모의 두 대각선은 각각 x축과 y축에 평행해야 합니다.
- 마름모의 네 꼭짓점은 모두 정수 좌표를 가져야 합니다.
예제
예제 1
입력 − 길이 = 3, 너비 = 3
출력 − 주어진 크기의 직사각형 내부에 만들 수 있는 마름모의 개수: 4
설명 − 아래 그림은 높이와 너비가 각각 3인 직사각형입니다. 넓이가 0보다 크고, 대각선이 좌표축과 평행하며, 꼭짓점이 정수 좌표인 마름모는 총 네 개이며 각각의 꼭짓점은 다음과 같습니다.
첫 번째 : [(0,1), (2,1), (1,0), (1,2)] 두 번째 : [(1,1), (3,1), (2,0), (2,2)] 세 번째 : [(0,2), (2,2), (1,1), (1,3)] 네 번째 : [(1,2), (3,2), (2,1), (2,3)]
예제 2
입력 − 길이 = 2, 너비 = 3
출력 − 주어진 크기의 직사각형 내부에 만들 수 있는 마름모의 개수: 2
설명 − 높이 2, 너비 3인 직사각형 안에는 위 조건을 만족하는 마름모 두 개를 만들 수 있습니다.
접근 방법
대각선이 x축, y축과 평행해야 한다는 조건 때문에 마름모의 모양은 수평 대각선의 길이와 수직 대각선의 길이, 두 값만으로 완전히 결정됩니다. 또한 모든 꼭짓점이 정수 좌표를 가지려면 대각선의 길이는 반드시 짝수여야 합니다. 따라서 수직 대각선의 길이 i와 수평 대각선의 길이 j를 2부터 시작해 2씩 늘려 가며 탐색하고, 각 경우마다 마름모가 놓일 수 있는 위치의 수는 (높이 − i + 1) × (너비 − j + 1)이 됩니다. 이 값을 모두 더하면 정답을 구할 수 있습니다.
- 높이와 너비를 정수로 입력받습니다.
- possible_rhombus(int height, int width) 함수는 직사각형의 크기를 받아 조건을 만족하는 마름모의 개수를 반환합니다.
- count 변수를 0으로 초기화합니다.
- i를 2부터 height까지, j를 2부터 width까지 2씩 증가시키며 이중 반복문을 수행합니다.
- 각 i, j에 대해 temp_1 = height − i + 1, temp_2 = width − j + 1을 계산합니다.
- temp_1 × temp_2 값을 count에 누적합니다.
- 반복이 끝나면 count를 결과로 반환합니다.
이 알고리즘의 시간 복잡도는 O(height × width)이며, 마름모의 개수가 빠르게 커질 수 있으므로 결과는 long long 타입에 저장하는 것이 안전합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
long long possible_rhombus(int height, int width){
long long count = 0;
for (int i = 2; i <= height; i += 2){
for (int j = 2; j <= width; j += 2){
int temp_1 = height - i + 1;
int temp_2 = width - j + 1;
count += temp_1 * temp_2;
}
}
return count;
}
int main(){
int height = 4, width = 4;
cout<<"주어진 크기의 직사각형 내부에 만들 수 있는 마름모의 개수: "<<possible_rhombus(height, width);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
주어진 크기의 직사각형 내부에 만들 수 있는 마름모의 개수: 16
높이와 너비가 각각 4인 직사각형에서는 조건을 만족하는 마름모가 총 16개 나오는 것을 확인할 수 있습니다.