[백준알고리즘] 2163번: 초콜릿 자르기 -Python

[백준알고리즘] 2163번: 초콜릿 자르기 -Python

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

2163번: 초콜릿 자르기

처음에는 Dynamic Programming 방식으로 풀었다. 

 

NxM크기의 초콜릿을 우선 가로방향으로 잘라주며 (N//2)xM과 (N-N//2)xM 크기의 초콜릿으로 나눠주었고 각각 1x1크기로 나눌 수 있는 경우의 수의 합에 1을 더해주었다.

이후 세로방향도 마찬가지로 해주면서 메모이제이션을 통해 문제를 풀었었다.

 

하지만 굳이 이렇게 풀지 않아도 된다. 가로방향을 먼저자르든지 세로방향을 먼저 자르든지 항상 결과가 같은 것을 보고 구해지는 식을 찾았다.

 

가로방향으로 먼저 자른다고 했을 때, 나올 수 있는 경우의 수는 (N-1) * M + (M-1) = N*M - M + M - 1 = N*M - 1 이다.

 

따라서 N*M - 1을 출력하면 최소 쪼개는 횟수가 출력된다.

 

n, m = map(int, input().split())
print(n*m-1)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다