[ Level 2 ] 멀쩡한 사각형 - 파이썬

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

 

제한사항

• W, H : 1억 이하의 자연수

---

점선이 지나는 점의 개수는 w와 h의 최대공약수이다.

다음과 같이 w,h이 8, 12일 때, 지나는 점의 개수는 둘의 최대공약수인 4이다.

 

그럼 여기서 최대공약수가 1인 경우와 1이 아닌 경우를 봐야한다.

 

1. 최대 공약수 = 1

최대 공약수가 1이라면 사각형 내에서 지나는 점이 없다. 그럼 대각선은 w+h-1의 수만큼 사각형을 지나간다.

 

2. 최대 공약수 >1

이때는 최대공약수 만큼 반복되는 영역이 생긴다.

이 영역 안에서는 최대 공약수=1인 경우가 반복되는 것이므로 이를 수식으로 표현한다면,

g * ((w//g) + (h//g) - 1) = w+h-g

 

결국 1번의 경우도 최대 공약수가 1이므로 위의 두 경우는 w+h-g으로 나타낼 수 있다.

 

따라서, 이 문제에 대한 답인 전체 사각형의 개수에서 잘라지는 사각형의 수를 뺀 수는 w*h - (w+h-g) 이다.

 

이를 코드로 나타내면,

 

 

def solution(w,h):
    def gcd(x, y):
        if y > x:
            x,y = y,x
        while y:
            x, y = y, x % y
        return x
    return w*h - (w+h-gcd(w,h))