두 개의 숫자 n과 m이 주어지며, 이는 n × m 크기의 보드를 나타냅니다. 또한 무한개의 1 × 2 크기 도미노가 있다고 가정합니다. 이때 도미노끼리 서로 겹치지 않고, 모든 도미노가 보드 안에 완전히 들어오도록 배치할 수 있는 최대 도미노 개수를 구하는 것이 문제입니다.
예를 들어 n = 5, m = 3이 입력으로 주어진다면, 출력은 7이 됩니다.
해결 접근 방법
이 문제는 의외로 간단한 수학적 직관으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 각 도미노는 정확히 2칸을 차지합니다.
- 따라서 보드의 전체 칸 수(t = n × m)를 2로 나눈 몫이 곧 배치 가능한 최대 도미노 개수입니다.
만약 보드의 전체 칸 수가 홀수라면 한 칸은 비어 있게 되지만, 나머지 칸들은 모두 도미노로 채울 수 있습니다. 반대로 칸 수가 짝수라면 보드 전체를 빈틈없이 덮을 수 있습니다.
알고리즘 단계
- t := n * m (보드의 전체 칸 수 계산)
- (t / 2)의 몫을 반환합니다.
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
구현 예시
class Solution:
def solve(self, n, m):
t = n * m
return t // 2
ob = Solution()
print(ob.solve(5,3))
입력
5,3
출력
7
복잡도 분석
이 알고리즘은 곱셈과 나눗셈 연산만 수행하므로 시간 복잡도는 O(1), 공간 복잡도 역시 O(1)입니다. 보드의 크기와 무관하게 항상 일정한 시간 안에 답을 구할 수 있습니다.