종이의 크기가 길이 L, 너비 B가 주어집니다. 또한 작은 직사각형의 크기가 주어집니다. 길이는 l이고 너비는 b입니다. 목표는 한 장의 종이에서 자를 수 있는 작은 직사각형의 최대 수를 찾는 것입니다.
우리는 다음 단계를 수행할 것입니다 -
-
먼저 수평 정렬, 시트 및 직사각형의 길이 L 및 l을 각각 취합니다. L을 l로, B를 b로 정렬하고 직사각형을 세십시오.
-
그런 다음 수직 정렬에서도 동일한 작업을 수행합니다. 다시 계산합니다. count의 최대값을 반환합니다.
예를 들어 이해합시다.
입력
Sheet L=18, B=6 Rectangle l=4, b=3
출력
Maximum rectangles: 8
설명
Horizontal 18/4=4 6/3=2 2*4=8 rectangles possible Vertical 18/3=6 6/4=1 6*1=6 rectangles possible Maximum rectangles here is 8
입력
Sheet L=10, B=6 Rectangle l=4, b=2
출력
Maximum rectangles: 6
설명
Horizontal 10/4=2 6/2=3 2*3=6 rectangles possible Vertical 10/2=5 6/4=1 5*1=5 rectangles possible Maximum rectangles here is 6
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
Length 및 Breadth 변수는 시트의 치수를 저장하는 데 사용됩니다.
-
len 및 bre 변수는 직사각형의 치수를 저장하는 데 사용됩니다.
-
함수 maxRectangles(int L, int B, int l, int b)는 시트와 사각형의 크기를 가져와서 가능한 최대 사각형 수를 반환합니다.
-
numh 및 numv 변수는 가로 및 세로로 자를 수 있는 사각형의 수를 저장하는 데 사용됩니다.
-
가로의 경우 cols=L/l 및 rows=B/b, 직사각형 가능, numh=cols*rows로 나눕니다.
-
세로의 경우 cols=L/b 및 rows=B/l, 직사각형 가능, numv=cols*rows로 나눕니다.
-
위의 두 단계 numh 또는 numv에서 얻은 결과로 최대값을 반환합니다.
예시
#include <stdio.h>
int maxRectangles (int L, int B, int l, int b){
int numh = 0, numv = 0;
// Cut rectangles horizontally if possible
if (l <= L && b <= B){
// One rectangle is a single cell
int cols = B / b;
int rows = L / l;
// Total rectangles = total cells
numh = rows * cols;
}
// Cut rectangles vertically if possible
if (l <= B && b <= L){
int cols = L / b;
int rows = B / l;
numv = rows * cols;
}
// Return the maximum possible rectangles
return numh>numv?numh:numv;
}
// Driver code
int main (){
int Length = 18;
int Breadth =6;
int len = 4, bre = 3;
printf("Maximum rectangles: %d",maxRectangles(Length,Breadth,len,bre));
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Maximum given sized rectangles that can be cut out of a sheet of paper: 8