백준 2163 - 초콜릿 자르기(JAVA)

2163번: 초콜릿 자르기 (acmicpc.net)

2163번: 초콜릿 자르기

 

문제는 위와 같다. 상당히 장황하게 뭘 써놓다보니 문제 이해가 잘 안되어서 좀 오랫동안 들여다 보았던 것 같다. 예를 들어서 생각해보면 너무 간단해서 당황할 정도 였다.

 

 

이런 초콜릿이 있다고 생각해보자. 가로는 4, 세로는 3 이라 할 때, 세로를 먼저 잘라보면 2번 자르게 된다.

그렇다면 가로는 어떻게 될까? 이미 2번 잘라서 3개로 잘려진 곳에서 3번을 자르면 되니 3*3 = 9, 총 9번을 자르면 된다. 이렇게 두가지를 더하면 11번 자르면 된다는 것을 알 수 있다. 

 

이제 이것을 그대로 미지수로 나타내어 보자. 가로가 M, 세로가 N일때 세로는 N-1번 자르게 된다. 가로는 N*(M-1)번 자르게 된다. 총 절단 횟수는 N-1 + N*(M-1)이 되는 것을 알 수 있다.

 

이것을 그대로 코드로 옮겨보면 

 

이렇게 간단하게 문제를 해결할 수 있다. 문제를 이해하기 어려워서 브론즈 1 단계인듯한 문제였다. 코드는 너무 간단해서 당황할 정도...