프로그래머스 - 종이 자르기

알고리즘/프로그래머스 1단계

게임만드는학생 2023. 9. 6. 15:10

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

#include <string>
#include <vector>

using namespace std;

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

M * N 의 종이를 1*1 로 전부 자르기 위해서 몇번의 가위질이 필요한지를 구하는 문제이다.

1. 가로 즉 M번 가위질을 해서 1 * N 의 종이를 M개 만든다.

2. 그리고 1 * N 의 종이를 M 번 자른다.

예를 들어, 길이가 5인 종이이면 4번을 잘라야 5조각이 된다.

따라서 우선 M - 1번을 자른다.

그 후에, 1 * N 종이도 N - 1 번 자르면 1*1 종이가 나온다.

이 작업을 M 번 반복하니 ( N - 1 ) * M 이다.

따라서 총 M - 1 + ( N - 1 ) * N 번 잘라야 한다.