[프로그래머스 Lv2,python] - 멀쩡한 사각형

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

프로그래머스

def gcd(a,b): #최대 공약수.유클리드 호제법 사용
    if a%b==0:
        return b
    return gcd(b,a%b)

def solution(w,h):
    res = w * h - (w + h - gcd(w, h))
    return res

 

사각형들이 패턴을 가진채 잘려진다. 

이것이 4번 반복되는데, 가로의 길이인 8과 세로의 길이인 12의 최대공약수인 4만큼 반복되는것을 알 수 있다.

=> 작은 사각형의 가로 길이를 w', 세로 길이를 h' 라고 할 때 각각 ( w//최대공약수),(h//최대공약수)의 값을 가진다. 

이때 직선과 세로의 선이 만나는 갯수는 1개이고, 가로의 선이 만나는 갯수는 2개이다.

=> w'-1 개와 h'-1개 이다. 

첫 점을 고려하면 (w'-1) + (h'-1) + 1 = w' + h' - 1 이 나온다.

 

이것이 최대공약수만큼 반복되므로,

사용하지 않는 사각형은 ( w' + h' - 1 ) * k = w + h - k이 된다.