[자바] 프로그래머스 - 종이 자르기 (Lv0, Java)

문제 : Programmers-종이 자르기

문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

필요 알고리즘 개념

• 수학
  • 수학문제긴한데, 몇 개 공책에 그려보다보면 규칙성은 어렵지 않게 찾을 수 있을 것 같다.

 

  '종이를 겹쳐서 자를 수 없습니다.' 부분이 가장 중요한 조건이다. 이게 가능했다면 그리디 알고리즘쪽으로 갔을텐데, 겹쳐서 자를 수 없다고 했으므로 규칙성을 찾아봐야 한다. 아무튼 겹쳐서 자를 수 없으니 결국은 한땀한땀 자를 수 밖에 없다. 아래와 같이 4x3 짜리 종이를 생각해보자.

 

  이걸 우선 가로방향으로 n개로 쪼개보자. 이 경우 n-1번 쪼개면 된다. 그리고 그 중 한 개만 세로방향으로 쪼개보자. m-1번 쪼개면 된다. 그런데, m-1번 쪼갠게 처음 n-1번 쪼갠 n개의 조각 하나이므로 총 n개의 조각을 m-1번 쪼개야 한다.

  따라서 처음에 가로로 쪼갠 경우, 답은 n-1 + n(m-1) 이 된다.

그럼 처음에 세로로 쪼갠 경우는 어떻게 될까? m-1 + m(n-1)이 된다.

근데 둘다 식을 풀어보면 전자는 n-1+nm-n = nm-1

후자는 m-1+mn-m = nm-1 이다.

 

  따라서 어느쪽을 먼저 자르더라도 nm-1이 답임을 알 수 있다.

 

 

 

코드 : github

/**
 * 문제 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
 */
class Solution {
    public int solution(int M, int N) {
        return M*N-1;
    }
}