멀쩡한 사각형

문제 설명

1 x 1 크기의 격자칸으로 구성된 가로 길이가 W, 세로 길이가 H인 직사각형 종이를 왼쪽 위에서 오른쪽 아래 대각선으로 자를 때, 잘리지 않은 칸의 개수를 구한다.

예시

위 그림에서 색칠되지 않은 칸의 개수를 구하면 80칸이다.

풀이

아이디어

1. 구하려는 값은?

=> 구하려는 값 = 전체 칸의 개수 - 잘린 칸의 개수 = W * H - 잘린 칸

2. 잘린 칸의 개수는?

파란 삼각형과 초록 삼각형은 닮음 관계이다. 따라서 파란 삼각형의 빗변의 길이를 알면 초록 삼각형의 빗변도 알 수 있다. 이 때 파란 삼각형의 한 변의 길이는 초록 삼각형의 한 변의 길이 / 초록 삼각형의 가로, 세로의 최대공약수와 같다. 따라서 그림에서 파란 삼각형의 가로, 세로는 2, 3이다.

파란 삼각형의 가로, 세로인 2 x 3 크기의 사각형 중, 삼각형의 빗변으로 인해 잘린 칸들은 가장 왼쪽 위 칸에서 아래, 오른쪽 순으로 지그재그를 그리며 가장 오른쪽 아래 칸으로 가는 경로와 같다. 이 경로의 칸의 개수는 가장 왼쪽 위 칸에서 가장 아래 오른쪽 칸으로 가는 최단 거리와 같다. 따라서 잘린 칸의 개수는 가로 길이 + 세로 길이 - 1 = 2 + 3 - 1 = 4 과 같다.

파란 삼각형의 빗변으로 잘린 칸의 개수는 초록 삼각형의 가로, 세로의 최대공약수의 개수만큼 반복되므로, 총 잘린 칸의 개수는 파란 삼각형에서 잘린 칸의 수 최대공약수 = 4 4 = 16 개이다.

3. 최대공약수를 구하려면?

유클리드 호제법을 이용한다.

유클리드 호제법

위키백과 - 유클리드 호제법 을 참고했습니다.

코드

def solution(w, h):
    def get_gcd(a, b):
        while b > 0:
            a, b = b, a % b
        return a
    
    gcd = get_gcd(w, h)
    
    # (w * h) - (w / gcd + h / gcd - 1) * gcd
    return (w * h) - (w + h - gcd)