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

문제

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

프로그래머스

 

내 풀이 A

def solution(M, N):
    return M*N-1

예시들과 몇가지 따로 만든 예시들로부터 귀납 추론을 통해 N*M-1이면 답을 얻을 수 있는 결과가 나왔지만

이건 아닌 것 같아 다른 방법을 찾아보았다.

 

내 풀이 B

def solution(M, N):
    M, N = min(M, N), max(M, N)
    if M == 1:
        return N-1
    return 1+solution(M-1, N)+solution(M-(M-1), N)

다른 풀이에서 힌트를 얻었는데

종이에 가위질 한 번 할 때마다 

1 + 잘린 종이 A + 잘린 종이 B

가 되는 상황을 생각해 재귀 함수로 만들었다.

M을 세로로 생각하고 N을 가로로 생각했는데

세로가 1일 경우 남은 가로 길이에 대해 -1 하면 모두 1x1로 만들었을 때 나오는 종이의 개수와 같아지므로 

M == 1일 경우 return N-1이 됐고

 

M이 1이 아닐 경우 가로로 길게 한번 자른다면

종이 조각 A는 세로가 세로 - 1이 되고

나머지 종이 조각 B의 세로는 위에서 자르고 남은 세로 - 1 만큼 자른 값이 된다.

가로 길이는 그대로

 

이걸 코드로 나타낸게 위의 코드다.