[coding_test]멀쩡한 사각형

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

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

문제에서 나온 사각형의 예시를 보고, 어떻게 하면 구할 수 있지? 라고 생각을 좀 오래 했던것 같다.

계속 보다 위처럼 규칙을 발견할 수 있었고,

수많은 사각형을 그려보고 결론을 도출했을 때 같은 수로 나눠 최소로 사각형을 만들어 (가로+세로-1)은 못만드는 사각형이고,

나눈 수로 곱해주면 값이 나온다

같은 수로 나눠 최소로 만드는 것을 도출했지만.. 난 최대공약수라는 아주 기초적인 수학 공식을 생각해 내지 못했지만 

역시 검색을 통해 최대공약수를 기억해 낼 수 있었다. 

 math모듈의 gcd를 불러와 문제를 풀었더니 정답~~

from math import gcd
def solution(W,H):
    return W*H - (W+H -gcd(W,H))

---

문제 풀이 후 

- 최대 공약 수에 대해 조금 더 알게 되었다. 

- 모든 문제는 규칙이 생기고, 규칙을 알면 어떻게 푸는지 쉬워진다.