문제

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

문제풀이

문제의 제한조건이 1억 이하라고 할 때부터 수학적 사고력을 요하는 문제라는 감이 왔던 문제이다. 한시간동안 고민해보고 풀이법이 떠오르지 않아 다른 사람의 풀이를 참고하였다.

문제를 푸는데 핵심이 되는 것은 최대공약수 찾기와 대각선이 지나가는 사각형의 개수를 구하는 방법이다. 솔직히 최대공약수는 패턴을 조금만 관찰하면 누구나 찾을 수 있지만, 사각형의 개수를 구하는 방법을 보면서 감탄했었다. 이번 문제의 풀이는 관련 링크에 자세하게 나와있으니, 풀이만 올려본다.

def gcd(a, b):
    if a < b:
        a,b = b,a
        
    rest = 1e3
    while rest != 0:
        rest = a % b
        a, b = b, rest
    
    return a


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