[Python] 백준 2163번 초콜릿 자르기

1. Question

 

N*M의 초콜릿을 쪼개어 1*1의 초콜릿을 만드는 문제입니다.

 

2. Code

a, b = map(int, input().split())

print(a*b-1)

 

 

3. Solution

1. a와 b를 입력받는다.

3. 초콜릿을 쪼갤 수 있는 최소 수를 구하여 출력한다.

 

 

그림판으로 초콜릿을 얼마나 쪼갤 수 있는지 수를 구하여 봤는데 모든 경우의 수가 n*m 수보다 1 작았습니다. 설마설마 하며 제출하니까 맞았다고 나오더라구요. 

다시 제대로 식을 세워서 해봤습니다.

 

이렇게 가로가 m, 세로가 n인 3*2의 초콜릿이 있다고 가정하겠습니다.

만약 초콜릿을 세로로 먼저 자를 경우, m-1번인 2번을 자르게 됩니다.

이제 가로로 자르겠습니다.  잘려진 초콜릿은 총 3조각입니다. 이 3조각을 n-1번인 한번씩 잘라야 합니다. 그렇게 되면 3*1번, 즉 m*(n-1)번씩 자르게 됩니다.

 

전체적인 식을 세우면 (m-1)+m*(n-1)번입니다. 처음에 세로로 먼저 잘랐었는데 가로로 먼저 잘라도 같은 식이 나왔습니다. 가로로 먼저 자른 식은 (n-1)+n*(m-1)이었습니다. 

 

(m - 1) + m * (n - 1) = (n - 1) + n * (m - 1)

m - 1 + nm - m = n - 1 + nm-n

nm - 1 = nm - 1

 

이라는 결론에 도달하였습니다. 결국 제가 처음에 세운 식과 같다고 할 수 있습니다. 그림을 그려가면서 풀었는데 식으로도 맞다니 기분이 묘하네요.

 

---

 

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

2163번: 초콜릿 자르기