초콜릿 자르기

면접 대비

시간 제한2초메모리 제한128 MB

요약
N x M 초콜릿을 모두 1x1 조각으로 나누는 데 필요한 최소 절단 횟수를 구합니다.
난이도

쉬움10점 중 1점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

정화는 N×MN \times M 크기의 초콜릿 한 개를 가지고 있다. 이 초콜릿에는 가로와 세로로 금이 그어져 있어, 모두 자르면 1×11 \times 1 크기의 조각 N×MN \times M개로 나눌 수 있다.

정화는 친구들과 나눠 먹기 위해 초콜릿을 전부 1×11 \times 1 크기로 쪼개려고 한다. 한 번 쪼갤 때는 현재 가지고 있는 초콜릿 조각 하나를 고르고, 그 조각에 그어진 금 중 하나를 따라 자른다. 그러면 그 조각은 두 조각으로 나뉜다.

초콜릿은 자르는 동안 녹을 수 있으므로, 정화는 자르는 횟수를 최소로 하고 싶다. 초콜릿의 크기 NN과 MM이 주어졌을 때, 모든 조각을 1×11 \times 1 크기로 만들기 위한 최소 자르기 횟수를 구하라.

입력

첫째 줄에 두 정수 NN과 MM이 주어진다. (1≤N,M≤300)(1 \le N, M \le 300)

출력

초콜릿을 모두 1×11 \times 1 크기로 만들기 위한 최소 자르기 횟수를 출력한다.

예제2

  1. 예제 1

    입력
    2 2
    
    예상 출력
    3
    
  2. 예제 2

    입력
    1 1
    
    예상 출력
    0