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

📕 문제

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

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

 

💡 풀이법

먼저 나는 세로와 가로 중 긴 쪽을 세로로 두고 도형을 봤다.

(어차피 가로 세로 바껴도 상관이 없기 때문)

먼저 세로 길이만큼 사각형이 잘린다고 생각하고 해당 사각형을 빼고 나면 초록색으로 체크한 사각형만 남는다.

보면 격자 교점지나지 않고 사각형의 벽을 가르는 점이 생겼을 때 그 옆에 사각형이 생긴 것을 볼 수 있다.

현재 위의 사각형에서는 빨간 점이 위에서부터 1.5 (12/8) 간격으로 생기는 것을 알 수 있다.

그런데 같은 패턴이 4번 반복 되고 있기 때문에 첫번째 패턴의 사각형만 보자.

2 X 3의 사각형에서는 세로로 빨간점이 가로의 길이(2)만큼 생기지만 마지막 빨간점은 사각형의 끝점이기때문에 빼면 첫번째 사각형 패턴에서는 잘린 사각형이 3+2-1만큼 생긴다.

하지만 이 사각형 패턴이 전체 사각형에서 4번 반복되기 때문에 4(2+3-1)이 된다.

패턴의 개수는 가로와 세로 길이의 최대공약수만큼 생긴다. 최소공약수를 G라 하자.

식을 일반화 시키면 잘린 사각형의 개수 = G(가로/G + 세로/G -1) 이 된다...?

더 일반화 시키면 잘린 사각형의 개수 = 가로 + 세로 - G 가 된다!!

 

ex) 3 X 5 사각형

파란색 사각형의 개수 = 세로의 길이 (=5)

초록색 사각형의 개수 = 가로의 길이-1 (=3-1)

=> 위의 사각형에서 잘린 사각형의 개수 = 5+3-1

만약 6 X 10 사각형일 경우 위와 같은 패턴이 2번 반복되기 때문에 2(5+3 -1)가 된다.

 

결국 멀쩡한 사각형은 가로X세로-(가로+세로-가로와 세로의 최대공약수) 가 된다.

 

def solution(w,h):
    def GCD(x, y):
        while(y):
            x, y = y, x % y
        return x
    g = GCD(w, h)
    return w*h -(w+h-g)