C++로 체스판을 두 조각으로 나누지 않고 만들 수 있는 최대 컷 수 구하기

개념

A×B 크기의 체스판이 주어졌을 때, 체스판이 두 개의 조각으로 나뉘지 않도록 만들 수 있는 최대 컷(칼집)의 개수를 계산하는 것이 이 문제의 목표입니다.

예시

입력:

A = 2, B = 4

출력:

최대 컷 수 = 3

입력:

A = 2, B = 2

출력:

최대 컷 수 = 1

풀이 방법

• A = 2, B = 2인 경우에는 컷을 1개(빨간색 표시)만 만들 수 있습니다. 여기에 컷을 하나 더 추가하면 체스판이 두 조각으로 갈라지게 됩니다.

• A = 2, B = 4인 경우에는 컷을 3개(빨간색 표시)까지 만들 수 있습니다. 마찬가지로 하나라도 더 추가하면 체스판이 두 부분으로 나뉩니다.

위의 결과들을 관찰해 보면 다음과 같은 규칙을 도출할 수 있습니다.

최대 컷 수 = (A − 1) × (B − 1)

즉, 각 행과 열 사이의 경계선 중 마지막 경계선 하나씩을 제외한 나머지 선들을 모두 자르면, 체스판은 여전히 하나의 조각으로 연결된 상태를 유지하면서 가장 많은 컷을 만들 수 있습니다.

C++ 코드 예제

// 위 접근 방식의 C++ 구현
#include <bits/stdc++.h>
using namespace std;
// 최대 컷 수를 계산하는 함수
int numberOfCuts1(int A, int B){
    int result1 = 0;
    result1 = (A - 1) * (B - 1);
    return result1;
}
// 드라이버 코드
int main(){
    int A = 4, B = 4;
    // 함수 호출
    int Cuts = numberOfCuts1(A, B);
    cout << "Maximum cuts = " << Cuts;
    return 0;
}

출력 결과

Maximum cuts = 9

위 예제에서 A = 4, B = 4일 때 (4−1) × (4−1) = 9가 되어, 체스판을 나누지 않으면서 최대 9개의 컷을 만들 수 있음을 확인할 수 있습니다. 시간 복잡도는 단순 곱셈 한 번으로 계산되므로 O(1)입니다.