[Python] 멀쩡한 사각형 - Summer/Winter Coding(2019)

<문제 링크>

 

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

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

 

---

<풀이>

위 그림에서 멀쩡한 사각형을 구하기 위해서는 대각선으로 깔끔하게 잘리는 사각형을 찾아야 한다.

그러기 위해서는 최대 공약수를 구해 w와 h를 나누면 split_w, split_h가 구해지며 위 그림에는 최대 공약수 4로 나누어 2와 3이 구해진다. (2와 3으로 봤을 때 대각선으로 깔끔하게 잘리는 사각형 구하기 가능)

그런 다음 멀쩡한 사각형을 구하기 위해 멀쩡하지 않은 사각형 수를 구해 전체 사각형에서 빼주면 정답을 찾을 수 있다.

import math

def solution(w,h):
    can_use_square = 1
    
    gcd_num = math.gcd(w, h) # 2 * 3 으로 만들기 위해 최대공약수로 나누어야 함

    split_w = w // gcd_num # 2
    split_h = h // gcd_num # 3

    cant_use_square = (h // split_h) * (split_w + split_h - 1) # 축소 시킨 도형의 갯수 * 못 쓰는 정사각형
    total_square = w * h

    can_use_square = total_square - cant_use_square
    
    return can_use_square