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

문제

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

코딩테스트 연습 - 멀쩡한 사각형

 

풀이

from math import gcd

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

 

코드는 한 줄만에 끝났지만 정말 고민을 많이 하게 만든 문제였다.

대각선상에 있는 사각형의 개수에 무슨 규칙이 있을지 발견하기가 쉽지 않았던 것 같다. 

해답은 이러하다. w와 h의 최대공약수가 1인 직사각형의 경우, (w + h - 1)이 대각선상에 있는 사각형의 개수이다. 그 직사각형에서 높이 1당 하나씩, 넓이 1당 하나씩의 사각형을 지나게 되기 때문이다. 1을 빼는 이유는 첫 시작 사각형이 겹치기 때문이다. 이런 관점에서 볼 때, 최대공약수가 1이 아닌 사각형은 w + h에서 최대공약수만큼을 빼면 된다고 유추할 수 있다. (w + h - 1) 사각형이 대각선에 최대공약수만큼 존재할 테니까.