[프로그래머스] [C++] Lv.0 종이 자르기

Lv.0 종이 자르기

📌 문제 

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

프로그래머스

 

📌 풀이 

M*N 크기의 종이를 1*1 크기의 종이로 자를때 최소한의 가위질 횟수를 구하는 문제이다.

 

하나의 종이를 n개로 만드려면 총 n-1번의 가위질을 해줘야 한다.

즉, M*N 크기의 종이가 1*5 또는 5*1이라면 1*1 크기의 종이를 만들기 위해서는 5-1 = 4번의 가위질을 해줘야 한다는 것이다.

따라서 가로나 세로 둘 중 하나의 길이를 먼저 1로 만들어 두고 계산해야 최소 가위질 횟수를 구할 수 있다.

 

예를 들어 2*5 크기의 종이가 있다고 해보자.

먼저 종이의 가로 길이를 먼저 1로 만들어준다.(세로여도 상관없다) 가로 길이가 2이기 때문에 2-1 = 1번의 가위질을 해줘야 한다.

그 다음 세로 길이가 1이 되도록 가위질을 해줘야 한다. 세로 길이가 5이기 때문에 5-1 = 4번의 가위질이 필요하다.

그런데 처음에 종이의 가로 길이를 1로 만들어주는 과정에서 종이의 개수가 2개로 늘어났기 때문에 세로 가위질을 두번씩 해줘야 한다.

 

이해를 돕기 위해 그림으로 표현해 보았다.

 

즉, 최소한의 가위질 횟수는 (가로길이-1) + {(세로길이-1) * (가로길이)}가 된다.

이를 식으로 표현하면 다음과 같다.

(M-1) + ((N-1) * M))

 

📌 전체 코드 

풀이에서 도출한 식을 이용해 작성한 코드이다.

#include <string>
#include <vector>

using namespace std;

int solution(int M, int N) {
    int answer = 0;
    
    answer = (M-1) + ((N-1) * M);
    
    return answer;
}

 

📌 결과 

제출 결과 깔끔하게 통과했다 👍