[BOJ] 2163번 - 초콜릿 자르기
2163번: 초콜릿 자르기
정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와
www.acmicpc.net
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))"이다.
BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm