[Level 2] 멀쩡한 사각형

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

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

---

접근

입력되는 W와 H가 1억 이하의 자연수이다. 그래서 뭔가 탐색을 하여 답을 구할 수 없다고 생각을 하고 규칙을 찾아보려고 했다. 하지만 규칙을 찾지 못하였고 다른 사람들의 풀이를 참고하였다.

종이에 여러가지 테스트 케이스로 그림을 그려보았는데 꼭지점의 개수에 주목을 하였다. WxH에서 대각선을 그었을 때 꼭지점의 개수가 W와 H의 최대공약수였다. 

 

그렇다면 최대 공약수를 어떻게 활용할 수 있을까? 

전체 크기 WxH에서 대각선을 그었을 때 잘리지 않은 사각형들의 개수를 보면 전체 크기에서 (W+H-최대공약수)를 뺀 것과 같았다.

 

이러한 접근을 어떻게 할 수 있을지 많은 고민을 해봐야겠고 최대 공약수와 최소 공배수의 특징들도 정확하게 이해해야겠다. 뿐만 아니라 기초수학과 관련된 문제들에 많이 약한 것 같다.

 

구현

전체 크기 WxH에서 (W+H-최대공약수)를 빼주었다.

math에서 gcd가 있는 것을 알게되었다.

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