[프로그래머스] 멀쩡한 사각형 (level2, python)

 

 

🤔 풀이 코드

 

import math

def solution(w,h):
    return w * h - (w + h - math.gcd(w, h))

 

 

🤔 문제 풀이

 

코드가 짧아서 쉬운 문제처럼 보이지만, 왜 저런 식이 나왔는지 이해하는 것이 중요합니다.

문제에서 나온 이 예시를 한 번 봅시다.

 

 

가로 8, 세로 12의 사각형으로, 일정한 패턴이 반복되는 것처럼 보입니다.

 

위와 같은 가로 2, 세로 3의 사각형의 패턴이 여러 번 반복되는 것처럼 보이죠.

계산하면, 가로 8 세로 12의 사각형은, 가로 2, 세로 3의 사각형에서 선에 걸리는 사각형의 개수 * 4입니다.

여기서 4라는 숫자는, 8과 12의 최대 공약수인것을 알 수 있습니다. 또한 가로 2와 세로 3은 서로소 관계임을 알 수 있죠.

따라서 최대 공약수를 이용해서 문제를 풀어야겠다는 생각을 할 수 있습니다.

 

 

다시 변수로 바꿔서 생각을 해보겠습니다.

가로 w와 세로 h의 사각형이 있고, 최대공약수 k가 있다고 해봅시다.

그러면 가로 w, 세로 h의 사각형에서 각각 최대 공약수로 나눈 가로 w'와 세로 h' 사각형으로 만들 수 있겠죠.

 

이제 직선과, 사각형의 변이 만나는 수를 계산해봅시다.

 

 

위의 사각형은 가로 w', 세로 h'인 사각형입니다. 대각선을 그었을 때, 기존의 사각형과 선이 만나는 변은,

가로변 h' - 1개, 세로변 w' - 1개만큼 만납니다. 그리고 이러한 변을 대각선이 꿰뚫어 나갈 때마다 새로운 사각형을 만나게 됩니다.

첫 점을 고려해서 한 개를 추가해 계산해보면, 가로 w', 세로 h'의 사각형에서 대각선과 만나는 사각형의 개수는,

(w' - 1) + (h' - 1) + 1 = w' + h' - 1이 나옵니다.

 

그럼, 이제 가로 w, 세로 h의 사각형의 경우도 대각선과 만나는 사각형의 개수를 구할 수 있습니다. (w' + h' - 1)에 최대 공약수 k를 곱하면 되죠.

kw' + kh' - k = w + h - k가 됩니다.

 

따라서 대각선과 겹치지 않는 사각형의 개수를 구하려면,

w * h로 전체 사각형의 수를 구한다음, w + h - k를 빼주면 됩니다.

코드로 바꾸면,

import math

def solution(w,h):
    return w * h - (w + h - math.gcd(w, h))

이러한 코드가 완성됩니다.