백준 2163 파이썬 - 초콜릿 자르기 (boj 2163 python)

문제 : boj2163

 

  쪼갠걸 겹쳐서 자를 수 없으므로, 결국 한땀한땀 자를 수 밖에 없다. 그럼 n x m 조각에 대해 n을 높이, m을 너비라고 생각해보자.

  이걸 우선 가로방향으로 n개로 쪼개보자. 이 경우 n-1번 쪼개면 된다. 그리고 그 중 한 개만 세로방향으로 쪼개보자. m-1번 쪼개면 된다. 그런데, m-1번 쪼갠게 처음 n-1번 쪼갠 n개의 조각 하나이므로 총 n개의 조각을 m-1번 쪼개야 한다.

  따라서 처음에 가로로 쪼갠 경우, 답은 n-1 + n(m-1) 이 된다.

그럼 처음에 세로로 쪼갠 경우는 어떻게 될까? m-1 + m(n-1)이 된다.

근데 둘다 식을 풀어보면 전자는 n-1+nm-n = nm-1

후자는 m-1+mn-m = nm-1 이다.

 

  따라서 어느쪽을 먼저 자르더라도 nm-1이 답임을 알 수 있다.

 

 

코드 : github

n,m=map(int,input().split())
print(n*m-1)