C 언어로 종이 한 장에서 잘라낼 수 있는 직사각형의 최대 개수 구하기

종이 한 장의 크기, 즉 길이 L과 너비 B가 주어지고, 잘라내고자 하는 작은 직사각형의 크기인 길이 l과 너비 b도 함께 주어집니다. 이 문제의 목표는 종이 한 장에서 잘라낼 수 있는 작은 직사각형의 최대 개수를 구하는 것입니다.

해결 과정은 다음과 같습니다.

• 가로 방향 배치: 종이의 길이 L에 직사각형의 길이 l을 맞추고, 너비 B에 너비 b를 맞춰 배치한 뒤 개수를 셉니다.

• 세로 방향 배치: 같은 방식으로 세로 방향으로 배치했을 때의 개수도 계산합니다.

• 두 경우 중 더 많은 개수를 결과로 반환합니다.

예시를 통해 살펴보겠습니다.

입력

종이 L=18, B=6 / 직사각형 l=4, b=3

출력

최대 직사각형 개수: 8

설명

가로 배치: 18/4=4, 6/3=2 → 4*2=8개 가능
세로 배치: 18/3=6, 6/4=1 → 6*1=6개 가능
따라서 최대 개수는 8개

입력

종이 L=10, B=6 / 직사각형 l=4, b=2

출력

최대 직사각형 개수: 6

설명

가로 배치: 10/4=2, 6/2=3 → 2*3=6개 가능
세로 배치: 10/2=5, 6/4=1 → 5*1=5개 가능
따라서 최대 개수는 6개

프로그램의 접근 방식

• 변수 Length와 Breadth는 종이의 크기를 저장합니다.

• 변수 len과 bre는 잘라낼 직사각형의 크기를 저장합니다.

• 함수 maxRectangles(int L, int B, int l, int b)는 종이와 직사각형의 크기를 인자로 받아 잘라낼 수 있는 직사각형의 최대 개수를 반환합니다.

• 변수 numh와 numv는 각각 가로 방향과 세로 방향으로 잘라낼 수 있는 직사각형의 개수를 저장합니다.

• 가로 배치의 경우, 열의 개수는 L/l, 행의 개수는 B/b로 계산하며, 가능한 개수는 numh = 열 × 행입니다.

• 세로 배치의 경우, 열의 개수는 L/b, 행의 개수는 B/l로 계산하며, 가능한 개수는 numv = 열 × 행입니다.

• 위 두 단계에서 얻은 값 numh와 numv 중 더 큰 값을 최종 결과로 반환합니다.

C 코드 예제

#include <stdio.h>
int maxRectangles(int L, int B, int l, int b){
    int numh = 0, numv = 0;
    // 가로 방향으로 자를 수 있는 경우
    if (l <= L && b <= B){
        // 하나의 직사각형은 하나의 칸에 해당
        int cols = B / b;
        int rows = L / l;
        // 전체 직사각형 개수 = 전체 칸의 개수
        numh = rows * cols;
    }
    // 세로 방향으로 자를 수 있는 경우
    if (l <= B && b <= L){
        int cols = L / b;
        int rows = B / l;
        numv = rows * cols;
    }
    // 가능한 최대 직사각형 개수 반환
    return numh>numv?numh:numv;
}
// 드라이버 코드
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 rectangles: 8

즉, 크기 18×6인 종이에서 4×3 크기의 직사각형을 최대 8개까지 잘라낼 수 있습니다. 이처럼 가로와 세로 두 가지 배치 방향을 모두 고려하여 더 많은 개수를 선택하는 것이 핵심입니다.