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

---

문제설명

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

코딩테스트 연습 - 멀쩡한 사각형

사고과정

• 주어진 문제 범위가 1억이라 DP문제일 것 같아서 어떻게든 규칙을 찾아내려 했다.. 그러나 실패했다..
• 질문하기 탭에 가서 보았는데, w, h의 최대공약수를 활용해서 푸는 문제였다..윾..
• 그래도 덕분에 파이썬으로 최대공약수를 구현하는 방법을 알게 되었다. 일명 유클리드 호제법! 
• 유클리드 호제법은 큰 수를 작은수로 나눈 나머지를 구한다. 그 나머지를 큰 수로 대체한다. 그런 다음 대소비교를 다시 해서 큰 수를 작은수로 나눈 나머지를 반복적으로 구한다. 계속 반복하다가 나누어 떨어질 때, 나눈 수가 최대공약수이다.
• 이를 다른 방식으로 구하자면, 큰 수에서 작은 수를 뺀다. 두 수가 같아질 때까지 반복.. 만약 같아졌다면 그 같아진 수가 최대공약수이다!
• 그리고 최대공약수를 구한 뒤 w * h 즉, 전체 사각형 개ㅅ에다가 w + h - 최대공약수 개수를 빼주면 정답이다..거의 수학문제를 푸는 듯 했다하하..

풀이

def solution(w,h):
    a, b = w, h
    
    while a != b:
        if a > b:
            a -= b
        else:
            b -= a
    gcd = a
    answer = w * h - (w + h - gcd)
    return answer