Python으로 n×m 직사각형 안에 배치할 수 있는 2×1 직사각형 개수 구하기

두 개의 값 n과 m이 주어졌을 때, 크기가 n×m인 직사각형 내부에 배치할 수 있는 크기가 2×1인 직사각형(도미노)의 개수를 구하는 문제입니다. 이때 반드시 고려해야 할 조건은 다음과 같습니다.

작은 직사각형끼리 서로 겹쳐서는 안 됩니다.
모든 작은 직사각형은 큰 직사각형 내부에 완전히 포함되어야 하며, 큰 직사각형의 가장자리에 닿는 것은 허용됩니다.

예를 들어 위 그림처럼 입력이 n = 3, m = 3이라면 출력 결과는 4가 됩니다.

풀이 접근 방식

크기가 2×1인 직사각형은 정확히 2칸의 면적을 차지합니다. 따라서 배치 가능한 최대 개수는 전체 면적 n×m을 2로 나눈 값과 밀접한 관련이 있습니다. 해결 절차는 다음과 같습니다.

n이 짝수(n mod 2 == 0)인 경우 → (n / 2) × m을 반환합니다.
그렇지 않고 m이 짝수(m mod 2 == 0)인 경우 → (m / 2) × n을 반환합니다.
n과 m이 모두 홀수인 경우 → (n × m − 1) / 2를 반환합니다.

핵심 원리는 간단합니다. 한 변이라도 짝수라면 도미노를 빈틈없이 나란히 배치해 전체 영역을 가득 채울 수 있습니다. 반면 n과 m이 모두 홀수일 때는 체스판처럼 배치했을 때 반드시 한 칸이 비게 되므로, 전체 면적에서 1을 뺀 후 2로 나누어 답을 구합니다.

예제 코드

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

def count_rect(n, m):
    if (n % 2 == 0):
        return (n / 2) * m
    elif (m % 2 == 0):
        return (m // 2) * n
    return (n * m - 1) // 2

n = 3
m = 3
print(count_rect(n, m))

입력:

3, 3