Baekjoon 문제 풀기 (2163번 : 초콜릿 자르기) Python

2163번 : 초콜릿 자르기

1. 문제읽기

---

규칙 찾기

초콜렛을 자를 때의 규칙을 찾아야 한다.
그림을 그려가며 풀었는데.. 세로로 무조건 자르는 것으로 고정하고 n,m의 초콜렛을 잘랐을 때 한번 자르면 n-1,m의 초콜렛과 1,m의 초콜렛으로 나누어진다는 것까지는 생각했다.
여기서 나는 동적계획법과 재귀의 개념을 사용해서 풀었는데 너무 간 것 같다 ㅋㅋㅋ
맞은 이유는 n,m이 300이하라는 작은 수였기 때문에 가능했던 것 같다.
아마도 큰 수가 들어가면 시간초과로 실패가 뜨지 않을까싶다.

2. 제출 코드

---

n, m = map(int, input().split())


def func(n, m):
    if n == 1:
        return m - 1
    return 1 + func(n - 1, m) + func(1, m)


print(func(n, m))

3. 공부할 것

---

규칙을 알고나니 바로 이해가 갔다.
print(N-1 + (M-1)*N) 가 그 규칙인데, 세로로 먼저 쪼갠다고 생각한다면 n보다 1번 덜 쪼갤 것이고 그 나눠진 조각은 n개가 나올 것이고 그 n개의 나눠진 조각은 각각 m-1번씩 쪼개진다.

그래도 혼자 힘으로 성공한 것으로 만족..