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

1. 문제

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

프로그래머스

 

2. 접근

1. 가로 or 세로 둘중 한개만 1이여도 사용 가능한 정사각형은 없어서 return 0을 해준다

2. w == h 라는 말은 정사각형이라는 말로, w * h 에서 y = x 선에 해당하는 정사각형들을 빼주면 된다

3. 직사각형의 경우 패턴을 사용하면 된다. 

- 종이에 예시로 그려보면 패턴들이 나온다.

- 최대공약수를 통해서 지울 수 있는 직사각형들을 구하고, 그 직사각형에서 양 끝쪽 모서리의 정사각형 하나씩은 사용할 수 있기에 -1씩 양 변에 해줘서 패턴내에서 지울 수 있는 총 정사각형 개수를 구한다

- 그래서 전체 크기에서 지울 정사각형 수를 빼주면 된다

 

3. 풀이

import math
def solution(w,h):
    answer = 1
    
    if (w == 1 or h == 1):
        return 0
    
    if w == h:
        return w * h - h
    else:
        g = math.gcd(w,h)
        
        ww = w // g
        hh = h // g
        
        cut = (ww*hh) - ((ww-1) * (hh-1))
        answer = w * h - (cut * g)
        
        return answer