[BOJ][C++] 백준 2163번 초콜릿 자르기

2163번 초콜릿 자르기

1. 문제 정보

백준 온라인 저지 [2163번 초콜릿 자르기] 문제의 링크입니다.

문제

정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.
초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.
초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력1

2 2

예제 출력1

3

시간 / 메모리 제한

2초 / 128MB

---

2. 생각

1. n X m의 초콜릿에서 n으로 먼저 자르든 m으로 먼저 자르든 n으로 자르다가 m으로 자르든 어차피 1X1을 만들어야하기 때문에 결론은 같게 되었습니다.

2. 따라서 n방향으로 자르면 n-1 번 자르면 1 X m의 크기로 잘린 초콜릿이 n개 생깁니다. 다시 1개를 m방향으로 자르면 m-1번 자르면 1X1의 크기로 잘립니다. 이 과정을 n번 합니다.

3. 따라서 (n-1) + n * (m-1)의 식이 나옵니다.

3. 소스코드 (C++)

---

터미널의 입출력 화면 예제1

터미널의 입출력 화면 다른 예제