초콜릿 자르기
면접 대비시간 제한1초메모리 제한128 MB
N x M 초콜릿을 행이나 열을 따라 완전히 잘라 모두 정사각형으로 만들 때 필요한 최소 조각 수를 구합니다.
문제
N행 M열 크기의 직사각형 초콜릿이 있다. 이 초콜릿을 여러 조각으로 잘라 친구들과 나누려고 한다.
자를 때에는 현재 남아 있는 직사각형 조각 하나를 골라, 행 사이 또는 열 사이의 한 직선을 따라 두 직사각형으로 나눈다. 모든 조각이 정사각형이 될 때까지 이 과정을 반복해야 한다.
가능한 한 적은 수의 정사각형 조각만 남기고 싶다. 초콜릿을 버리는 일은 없어야 한다.
위 그림은 N이 3이고 M이 4인 초콜릿을 자르는 두 가지 방법이다. 왼쪽은 정사각형 조각 6개가 남고, 오른쪽은 4개가 남는다. 오른쪽 방법이 가능한 최소 개수이다.
초콜릿의 크기 N과 M이 주어질 때, 만들 수 있는 정사각형 조각 개수의 최솟값을 구하시오.
입력
첫째 줄에 두 정수 N과 M이 주어진다. (1 <= N, M <= 1000)
출력
첫째 줄에 초콜릿을 잘라 만들 수 있는 정사각형 조각 개수의 최솟값을 출력한다.