[백준][C++] 2163번 초콜릿 자르기

초콜릿 자르기

$N \times M$크기의 초콜릿이 있을 때, 1x1크기의 초콜릿으로 쪼개기 위한 최소 횟수를 구하는 문제입니다.

초콜릿을 쪼갤 때 $1 \times 1$ 크기의 접선에서만 쪼갤 수 있다는 조건이 있습니다.

예를 들어, $2 \times 3$크기의 초콜릿은 총 6개의 $1 \times 1$ 조각으로 나누어주어야 합니다.
처음에는 1개의 덩어리에서 시작하며, 한 번 자를 때마다 조각이 1개씩 증가하므로 다음과 같은 과정을 거치게 됩니다.

이 예시로 초콜릿을 한 번 자를 때마다 조각의 개수는 1개씩 늘어난다는 것을 알 수 있습니다.

즉, 최소 횟수는 $N \times M - 1$번 쪼개야한다는 것을 알 수 있으며, 이것을 적용하여 문제를 풀이할 수 있습니다.

#include <iostream>

int main()
{
    int a{}, b{};
    
    std::cin >> a >> b;
    
    std::cout << a * b - 1;
}

시간 복잡도는 상수 시간에 끝나기 때문에 $O(1)$입니다.

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

메모리: 2020 KB

시간: 0 ms