백준 2163번 초콜릿 자르기

출처 : https://www.acmicpc.net/problem/2163

문제 ?

정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.

초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.

초콜릿을 쪼개다보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 횟수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 횟수를 구하는 프로그램을 작성하시오.

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

출력 : 최소 쪼개기 횟수

후기,

솔직히 난 수학적 사고 자신도 없고, 기피해서 이 문제 봐도 전혀 감이 안왔다..

남이 푼 것 봐도 엥? 하고 멍때리다 한 1-2시간은 쳐다보고 이해를 한 것 같다.

 서론이 길었지만, 문제 해석에 있어서의 팁은 최소 횟수에 초점을 맞추는 것이 아닌 '1×1 크기의 초콜릿으로 쪼개기 위한' 이 문장이 핵심이다

우리가 받은 직사각형의 초콜릿은 M(가로) X N(세로) 인데 절반으로 자르던! 끝부터 잘라나가던!  다 잘려 결국엔 1x1이 될 수 밖에 없다.

어느 방법이든 상관이 없다 이 얘기인데..

다시 돌아가서, 보다 쉬운 연산을 위해 끝에서부터 잘라나간다고 생각해보자

M 과 N이 몇이 되던 간에 초콜릿을 양손으로 잡고있다 왼손을 힘줘 끝부분을 세로로 똑 잘랐다. (1칸을 뗌)

떼어져나간 부분만 본다면 M(가로)는 1이고 세로는 N이다. 자 이걸 초콜릿 끝까지 반복하면? M-1번 반복을 하게 된다.

즉, M X 1 을 하기 위해 세로축을 떼는 전체과정이? M-1 번이다 이 말씀..

세로축을 다 떼냈으니 이제 가로축 차례다.

가로축을 이제 모두 1칸짜리로(1 X N) 분리하기 위해서는 이전과 같이 몇 회 나누어야 된다? N-1번!!

헌데 이 과정을 모두 몇 번 거쳐야 모두 1 X 1이 되는가? 총 나눠진 조각 갯수인 M개 이다. 

(세로가 아직 다 붙어있으니 N이 아니라 나눠진 1칸씩의 가로 갯수인 M이다.)

이렇게 1 X 1을 만들기 위한 과정이 모두 끝났다.

자 이제, 수식을 조합해보자. (M-1) + (N-1)*M = M-1 + NM-M = NM-1

이렇게 'NM-1' 이라는 정답이 나왔다. 

코드도 입력을 받아 저 식에 그대로 대입해 출력해주게 되면 정답으로 처리되는 것을 확인할 수 있다.

(코드도 필요하시면 댓글로 문의바랍니다~)