Python으로 푸는 백준 2163. 초콜릿 자르기

백준 2163. 초콜릿 자르기

정화가 N x M 크기의 초콜릿을 친구들과 나눠먹기 위하여 1 x 1 크기로 자르려고 한다.

최소 쪼개기 횟수로 초콜릿을 쪼개기 위해선 몇 번 쪼개야 하는지 구하는 프로그램을 작성하시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

Github에서 코드 보기

문제 풀이

이 문제는 크기마다 초콜릿을 쪼개는 수의 규칙을 찾아 문제를 풀 수 있다. 나는 수의 규칙을 찾아 문제를 풀었다.

가로가 N 조각이라는건 총 N-1 번 자르게 나눠져 있다는 점을 주의해서 문제를 해결하면 된다.

예를 들어, 5 x 3인 초콜릿이 주어졌다고 하자.

가로로 4 번을 잘라 1x3 짜리가 5조각이 나오고, 이 5조각을 각각 2 번씩 잘라야 1 x 1 짜리 초콜릿을 얻을 수 있다.

조건을 일반화 하면 N x M인 초콜릿이 주어졌다고 할 때,

가로로 (N-1)번 잘라 1xM 짜리가 N조각이 나오고, 이 N조각을 각각 (M-1)번씩 잘라야 1 x 1 짜리 초콜릿을 얻을 수 있다.

이를 식으로 만들게 되면 다음과 같다.

자르는 횟수  =  (N-1) + N(M-1)

파이썬 코드

 
import sys
input = sys.stdin.readline
 
def solve(n, m):
    return (n-1) + n * (m-1)
 
 
if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    print(solve(n, m))