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

최근에 문제를 많이 풀게 되면서 레벨 1을 다 풀고 이제 2로 넘어왔다.

( 패턴이 겹치는 문제는 안 올렸는데 필요하다면 댓글로 문의 바랍니다. )

 

프로그래머스 멀쩡한 사각형을 Python으로 풀어보겠다.

이 문제는 프로그래머스에서 2019년 출제된 코딩 테스트이다.

레벨은 2다.

---

문제

위와 같이 사각형의 w, h가 주어지면 그 사각형을 대각선으로 자르고

선에 의해 나눠지지 않은 멀쩡한 사각형의 수를 구하면 된다.

---

구현

맨 처음에 생각하는데 오래 걸렸다.

뭔가 규칙성이 보여서 작게 잘라 생각해봤다.

 

(8,12)의 사각형에서 위와 같은 (2,3)이 나온다.

닮음의 형태에서 반복되는 것을 알 수 있다.

 

이 형태에서 패턴이 반복하는 횟수는 최대공약수(4)이다.

 

그렇다면 한 패턴에서 지워지는 사각형 수는 어떻게 되는지 보자

 

현재 (2,3)에서 4개가 지워졌다.

가로 세로 각각 2, 3칸을 가며 대각선으로 지우기에 2+3-1 = 4 가 나온다.

 

이는 (1,3), (3,4)에서도 적용이 된다.

각각 지워야 할 것이 3+1-1=4, 3+4-1=6이 나온다.

 

이 방법이 이해가 힘들면 다른 방법을 생각해도 된다.

(8,12)에서 최대공약수로 (2,3)이 되면 기울기가 1.5이기 때문에 두 칸을 지우게 된다.(소수점은 올림으로 계산하면 됨)

2만큼 갈 것이기에 *2를 하면 2*2는 4가 나온다.

 

충분히 이해했을 거라고 보고 코드를 보겠다.

---

코드

def solution(w,h):
    big, small = max(w,h), min(w,h)
    while small:
        big, small = small, big%small
    return w*h-(w+h-big)

우선 유클리드 호제법을 이용해 다음과 같이 최대공약수를 뽑는다.

위에서 big이 최대공약수가 된다.

 

그리고 전체에서 지워진 개수를 빼면 정답이다.

---

이 문제는 코딩은 어렵지 않지만

수학적인 사고를 잘해서 패턴을 빨리 찾아내는 것이 포인트다.