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

문제

멀쩡한 사각형

문제 해설

w,h <= 1억 이기 때문에 O(w x h)의 시간 복잡도를 가지면 시간초과가 날 것이다. 처음 생각한 것은 w,h의 최대공약수를 구해서 w,h의 범위를 좁히고 답을 찾아나갈 생각이었지만, 두 수가 서로소인 경우는 이 방법이 통하지 않기 때문에 생각을 돌렸다.

아무리 생각해도 답이 나오지 않고 수학 문제라고 판단해서 답을 찾았다. 직선에 의해 잘린 사각형의 개수는 가로(W) + 세로(H) - G(최대 공약수) 이다. 실제로 최대공약수가 2 이상인 직사각형과 서로소인 직사각형, 정사각형 등등을 그려서 실험해 봤지만 모두 잘린 사각형의 개수가 위 식과 같았다. 결국 외우는 수 밖에 없다..

소스 코드

def GCD(a, b):
    gcd = 1
    small = a if a < b else b
    for i in range(2, small + 1):
        if a % i == 0 and b % i == 0:
            gcd = i
    return gcd

def solution(w,h):
    answer = w * h - (w + h - GCD(w, h))
    return answer