[프로그래머스/파이썬] 멀쩡한 사각형

 

나의 풀이

import math

def solution(w , h):
    if w == 1 or h == 1:
        return 0

    gcd = math.gcd(w, h)
    a, b = w // gcd, h // gcd
    count = 0

    for i in range(0, a):
        count += math.ceil(b * (i + 1) / a) - int(b * i / a)

    return w * h - count * gcd

 - 시간 초과 때문에 w나 h가 1일때 처리 해줌

 

최대공약수의 특징을 이용한 풀이

def gcd(a,b): return b if (a==0) else gcd(b%a,a)    
def solution(w,h): return w*h-w-h+gcd(w,h)

 - i 번째 줄과 i+1 번째 줄은 한 행만을 공유 -> 지워지는 블록의 개수는 w + h - 1

 - gcd만큼의 개수에서는 선이 아니라 점을 지나므로 + gcd