[Programmers] #120922 - 종이 자르기 [Java][C++][Python]

문제 링크

---

1. 아이디어

종이 자르기를 최소 가위질로 하려면 가로로 먼저 쭉 자른 후 남은 종이를 자르거나, 세로로 쭉 자른 후 남은 종이를 자르면 된다. 가로의 길이를 M, 세로의 길이를 N이라고 하면, 가로로 먼저 쭉 자르면 N - 1번의 가위질이 필요하고 각 N개의 종이를 세로로 자르는데 N * (M - 1)번의 가위질이 필요하다. 세로로 먼저 쭉 자르면 M - 1번의 가위질이 필요하고 각 M개의 종이를 가로로 자르는데 M * (N - 1)번의 가위질이 필요하다. 첫 번째 경우는 N - 1 + N * (M - 1)번의 가위질이 필요하고 두 번째 경우는 M - 1 + M * (N - 1)번의 가위질이 필요한데 두 경우 모두 식을 정리하면 M * N - 1번이므로 M * N - 1번의 가위질로 해결할 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int M, int N) {
        return M * N - 1;
    }
}

#include <bits/stdc++.h>
using namespace std;

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

def solution(M, N):
    return M * N - 1

---