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

종이 자르기

문제 링크

종이 자르기

분석

$M \times N$ 크기의 종이를 최종적으로 $1 \times 1$ 크기로 자르려고 합니다.

종이를 자를 때 한 번의 가위질로 한 장만 자를 수 있고, 여러 장을 겹쳐 자를 수 없습니다.
이때, 가위질 해야하는 횟수를 반환해야합니다.

$2 \times 2$ 크기의 종이를 $1 \times 1$ 크기로 자르려면 3번의 가위질이 필요합니다.
$2 \times 5$ 크기의 종이는 9번의 가위질이 필요합니다.
$5 \times 5$ 크기의 종이는 24번의 가위질이 필요합니다.

가위질의 횟수는 조각 수 - 1가 된다는 것을 알 수 있습니다.

가로는 $M - 1$번 자르고, 세로는 가로로 잘린 종이를 포함해 $N - 1$번 자르기 때문에 $M \times (N - 1)$번입니다.
정리하면, $(M - 1) + M \times (N - 1)$번입니다.

풀이

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

성능 요약

시간 복잡도는 $O(1)$입니다.

공간 복잡도는 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 3.63MB)
테스트 2 〉 통과 (0.01ms, 4.12MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 4.23MB)
테스트 5 〉 통과 (0.01ms, 4.19MB)
테스트 6 〉 통과 (0.01ms, 3.67MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.21MB)