멀쩡한 사각형( 파이썬 ) - 프로그래머스

격자 칸 1cm x 1cm로 이루어진 사각형이 주어져있고

 

해당 사각형의 대각선 꼭짓점 2개를 잇는 선이 그어질 때

 

선이 지나지 않는 1cm x 1cm 격자 칸의 개수를 구하는 문제이다.

 

문제

예시

8x12 직사각형에서 대각선이 지나는 격자의 개수를 반으로 나눠서 생각하면

(4x8 직사각형에서 대각선이 지나는 격자의 개수) x 2와 같고 이것을 또 반으로 나눠서 생각하면

(2x3 직사각형에서 대각선이 지나는 격자의 개수) x 4와 같다.

 

2와 3을 공통으로 나누는 2 이상의 자연수는 없으므로 2와 3은 서로소이고 8과 12를 서로소로 만든 수 4는 8과 12의 최대 공약수이다.

* a와 b를 c로 나누었을 때의 결과가 서로소라면 c는 a와 b의 최대 공약수임

 

따라서 전체 사각형에서 두 꼭짓점을 잇는 대각선이 지나는 격자의 개수는 아래와 같다.

두 수가 서로소일 때까지 나눈 뒤 (해당 직사각형에서 대각선이 지난 격자의 개수) x 최대 공약수

 

 

 

이제 우리는 a와 b가 서로소일 때 a x b 크기의 직사각형에서 대각선이 지나는 격자의 개수만 알면 문제를 풀 수 있다.

여러 개 그려보면 대각선이 지나는 격자의 개수는 n+m-1이라는 규칙을 찾을 수 있다.

 

따라서 가로 w 세로 h인 직사각형에서 두 꼭짓점을 잇는 대각선이 지나는 격자의 개수는 아까 구한 식

두 수가 서로소일 때까지 나눈 뒤 (해당 직사각형에서 대각선이 지난 격자의 개수) x 최대 공약수 에서

(w // 최대 공약수 + h // 최대 공약수 - 1) x 최대 공약수로 나타낼 수 있다. 식을 전개하면

w + h - 최대 공약수가 된다.

 

이 문제는 대각선이 지나지 않은 칸의 개수를 구하는 것이니 식은 아래와 같다.

대각선이 지나지 않은 칸의 개수 =

총 격자 칸 개수 - 대각선이 지난 칸의 개수 =

(w * h) - (w + h - 최대 공약수)

 

 

 

파이썬으로 작성한 답

def get_gcd(a, b):
    c = a % b
    
    if c:
        return get_gcd(b, c)
    else:
        return b

def solution(w, h):
    return (w * h) - (w + h - get_gcd(w, h))