Algorithm
백준 2163 - 초콜릿 자르기(JAVA)
Hyeon Lee
2022. 10. 5. 19:20
728x90
2163번: 초콜릿 자르기
정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿
www.acmicpc.net
문제는 위와 같다. 상당히 장황하게 뭘 써놓다보니 문제 이해가 잘 안되어서 좀 오랫동안 들여다 보았던 것 같다. 예를 들어서 생각해보면 너무 간단해서 당황할 정도 였다.
이런 초콜릿이 있다고 생각해보자. 가로는 4, 세로는 3 이라 할 때, 세로를 먼저 잘라보면 2번 자르게 된다.
그렇다면 가로는 어떻게 될까? 이미 2번 잘라서 3개로 잘려진 곳에서 3번을 자르면 되니 3*3 = 9, 총 9번을 자르면 된다. 이렇게 두가지를 더하면 11번 자르면 된다는 것을 알 수 있다.
이제 이것을 그대로 미지수로 나타내어 보자. 가로가 M, 세로가 N일때 세로는 N-1번 자르게 된다. 가로는 N*(M-1)번 자르게 된다. 총 절단 횟수는 N-1 + N*(M-1)이 되는 것을 알 수 있다.
이것을 그대로 코드로 옮겨보면
이렇게 간단하게 문제를 해결할 수 있다. 문제를 이해하기 어려워서 브론즈 1 단계인듯한 문제였다. 코드는 너무 간단해서 당황할 정도...
728x90