[js] 종이 자르기

머쓱이는 큰 종이를 1 x 1 크기로 자르려고 합니다. 예를 들어 2 x 2 크기의 종이를 1 x 1 크기로 자르려면 최소 가위질 세 번이 필요합니다.

정수 M, N이 매개변수로 주어질 때, M x N 크기의 종이를 최소로 가위질 해야하는 횟수를 return 하도록 solution 함수를 완성해보세요.

제한사항

• 0 < M, N < 100
• 종이를 겹쳐서 자를 수 없습니다.

나의 풀이

function solution(M, N) {
    return (M - 1) + (N - 1) * M;
}

사실... 이게 머야 ㅠ 하면서 종이에 하나하나 손으로 예시를 그려가면서 공식을 발견하려 노력해봤다. 그래서 나온 코드임...

1. 가로로 자르기 → M개의 1*N 크기 조각으로 자르기 위해서는 M-1번의 가위질이 필요하다.
2. 세로로 자르기 → 1N 조각을 N개의 11 조각으로 자르기 위해서는 각 조건마다 N-1번의 가위질이 필요하다. 우리가 가진 조각은 현재 총 M개 이므로 전체적으로 (N-1) * M번의 가위질이 필요하다.
3. 최종적으로 두 단계를 합치면 가로로 자르는 횟수 + 세로로 자르는 횟수 해서 위와 같은 공식이 도출된다.

다른 풀이

function solution(M, N) {
    return M*N-1;
}

아니 이게 이렇게 된다구요 선생님...? 사실 내가 쓴 코드의 식을 정리하면 이렇게 되긴 한다.

수학적 원리가 궁금할 뿐임...

전체 조각의 수: M x N 크기의 종이를 1 x 1 크기의 조각으로 나누기 위해, 종이를 (M x N)개의 조각으로 나눠야 합니다.
가위질 횟수: 종이를 M x N개의 조각으로 나누기 위해서는 총 M x N - 1번의 가위질이 필요합니다. 이는 왜냐하면 처음 종이는 한 덩어리로 시작하고, 각 가위질마다 하나의 새로운 조각이 생기기 때문입니다. 따라서, M x N개의 조각을 만들기 위해서는 M x N - 1번의 가위질이 필요합니다.

이건 그냥 뤼튼한테 물어봤다. 아하...