[프로그래머스] 멀쩡한 사각형

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

프로그래머스

🤔 문제분석

유클리드 호제법을 이용하여 접근합니다.

w와 h의 최대공약수를 구한뒤 가장 작은 w와 h를 구하고 공약수를 통하여 배율을 증가시켜 정답을 찾아냅니다.

배율이 가장작은 w와 h가 있을때 잘린 정사각형의 개수는 w+h-1 이 된다.

따라서 가장 작은 배율을 구한뒤에 그 다음 배율을 곱하여 결과를 얻어내면 끝.

💻 코드

def solution(w,h):
    # w > h
    w, h = max(w, h), min(w, h)

    def gcd(w, h):
        if h == 0:
            return w
        else:
            return gcd(h, w % h)

    g = gcd(w, h)

    ww = w // g
    hh = h // g

    cut = ww*hh - (ww-1)*(hh-1)

    return w*h - cut*g