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

안녕하세요 !

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

기울기를 이용하여 풀었습니다.

from math import gcd

def solution(w,h):
    g = gcd(w, h)
    
    ww = w // g
    hh = h // g
    
    r_sum = 0
    for x in range(1, ww):
        m = -hh / ww
        # print(m, hh, ww)
        r = int(m * x + hh)
        if r < 1:
            break
        r_sum += r 
        
    small_ans = ww * hh - r_sum * 2  
    
    return w*h - small_ans * g

사실 이 풀이가 완전한 풀이는 아닙니다. 프로그래머스에서 테케 돌렸을때 맞는 답이라고 나오기는 하지만..

문제에서 제한사항을 W, H 가 1억이하의 자연수라고 했습니다.

그러나 위의 풀이로 100000000, 99999999 을 구했을 때 시간초과가 납니다.

아래 풀이는 다른사람의 풀이를 참고해서 가져온 것입니다. 이 풀이는 좀… 예제를 보면서 생각을 해보니 이해는 가는데 생각해내기가 어렵네요 …ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이 풀이로 풀면 100000000, 99999999 의 답도 시간초과 없이 정확히 구할 수 있습니다.

from math import gcd

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