Python으로 체스판을 두 부분으로 나누지 않고 만들 수 있는 최대 컷 수 구하기

A × B 크기의 체스판(행렬)이 주어졌을 때, 체스판이 두 부분으로 나뉘지 않도록 하면서 만들 수 있는 최대 컷(자르기) 횟수를 계산하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 A = 2, B = 4라고 가정해 보겠습니다.

이 경우 출력은 3이 됩니다.

문제 해결 접근 방법

이 문제는 복잡한 알고리즘 없이 간단한 수식 하나로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 결괏값 res를 0으로 초기화합니다.
• res에 (M − 1) × (N − 1)을 대입합니다. 즉, 가로 칸 수에서 1을 뺀 값과 세로 칸 수에서 1을 뺀 값을 곱합니다.
• 계산된 res를 반환합니다.

A = 2, B = 4인 경우 (2 − 1) × (4 − 1) = 3이 되므로, 체스판을 두 조각으로 나누지 않으면서 최대 3번 잘라낼 수 있습니다.

예제 코드

아래의 파이썬 구현 예시를 살펴보면 이해가 더 쉽습니다.

def max_cuts_count(M, N):
    res = 0
    res = (M - 1) * (N - 1)
    return res

M, N = 2, 4
Cuts = max_cuts_count(M, N)
print(Cuts)

입력:

2, 4

출력

3