[BOJ] 2163번 - 초콜릿 자르기

2163번: 초콜릿 자르기

def chocoBBusher(n, m):
    l = n+m-2
    h = (n-1)*(m-1)
    return l+h


if __name__ == "__main__":
    n, m = list(map(int, input().split()))
    print(chocoBBusher(n, m))

---

문제 후기

일단 딱 보면 DP문제처럼 생겼다. 나도 요즘 DP문제를 풀다가 만난 문제라서 처음에는 DP로 풀어보려고 했다. 하지만 생각보다 그리 쉽지만은 않았다. 그리고 이 문제에서 신기한 점을 발견했다. 보통 처음 문제를 해결하려고 하면 어떤 걸 기준으로 자를지 생각해보게 된다. 그러다 보면 가로 세로 뭐든 한쪽을 기준으로 자를 때 최소가 된다는 것을 알 수 있다. 이때, 수학이 들어간다.

 

문제 풀이

일단 아래의 그림을 보자. 색이 칠해져 있는 선분들에 집중해볼 것이다. 왜냐하면 이 선분들이 이 직사각형의 초콜릿을 1 by 1로 만들기 위한 선불들이기 때문이다. 노란색을 기준으로 자른다고 하자. 그럼  빨간색 선분이 노란색 선분의 개수만큼 잘릴 거다. 그렇게 잘린 전체 선분의 총개수가 이 문제의 정답이다. 식으로 정리하면"전체 선분의 개수((n - 1) + (m - 1)) + 선분끼리의 교점의 수((n - 1) * (m - 1))"이다.

2 by 4 직사각형

DP로 풀어서 처음에 틀렸었다.

BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm