[Lv.0] 종이자르기

---

https://school.programmers.co.kr/learn/courses/30/lessons/120922

가로로 자르든 세로로 자르든 한 번에 쭉 자르고 나머지 조각들을 1X1에 맞게 자르는게 최소한의 가위질로 종이를 자를 수 있는 방법이다.

여기선 세로를 기준으로 일자로 자른 후 나머지 조각들을 1X1에 맞게 자를예정이다.

세로가 2 일땐 한번의 가위질 3일땐 두번의 가위질로 자를 수 있다 즉 일자로 잘라 세로가 1인 종이조각들을 만들기 위해서는

세로의 길이에서 1을뺀 (a-1) 번의 가위질이 필요하다는 것을 알 수 있다.

 

이제 세로가 1인 종이가 원래의 종이의 세로의 길이만큼(a) 나왔다.

이제 그 종이들을 가로로 자를것인데 이도 마찬가지로 1x1의 종이로 만들기 위해선 가로의 길이에서 1을 뺀 것(b-1)과 같은 가위질을 해야한다.

 

총 가위질의 횟수는 (a-1) + a(b-1)이 된다.

그래서 해당식을 그대로 적용해도 되고 좀더 풀어서 a*b-1을 리턴해주어도 값이 같게 나온다.

 

 

class Solution {
    public int solution(int M, int N) {
        int answer = 0;

        return M*N-1;
    }
}