프로그래머스 멀쩡한 사각형(Python)

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

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

이번 문제는 수학 문제였다. 처음에는 모든 경우의 수를 다 생각해서 가로, 세로, 사각형 개수의 관계를 찾아보려 애썼지만 깔끔하게 나오지 않았다. 그다음에는 작은 단위로 쪼개서 재귀적으로 풀 수 있지 않을까 하는 생각에 재귀를 호출할 기준을 찾으려 했지만 뭔가 애매하게 나와서 그만뒀다. 그러면 어떻게 하는 게 좋을 것인지 생각하다 시간이 많이 지나버려 결국 아래 사이트에서 배웠다.

https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python

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

이 사이트에서 보여준 코드는 정말 간단했다. 입이 다물어지지 않았다. 버려지는 사각형의 개수가 가로와 세로의 최대공약수와 관련이 있음을 발견해내셨다. 어떠한 과정을 통해 알아내셨는지 알아보자.

정답까지의 과정

먼저 프로그래머스의 예시와 똑같은 사각형을 그려보자.

가로는 8, 세로는 12인 격자 무늬의 직사각형에서 대각선을 그었을 때 대각선과 격자무늬의 꼭짓점이 만나는 곳을 기준으로 작은 사각형을 그려보자. 이 예시에서는 4개의 작은 직사각형이 나온다.

하나의 작은 직사각형을 확대해서 보자.

이 작은 직사각형은 가로는 2, 세로는 3인 격자 무늬의 직사각형이다. 여기서 쓸 수 없는 정사각형의 개수는 4개이다. 세 숫자를 통해 우리는 쓸 수 있는 정사각형을 구하는 하나의 수식을 만들 수 있다.

2 = 2 * 3 - (2 + 3 - 1)

이번에는 가로가 3, 세로가 4인 직사각형의 경우에도 위 처럼 식으로 표현할 수 있는지 살펴보자.

6 = 3 * 4 - (3 + 4 - 1)

위 두 가지를 통해 우리는 가로가 w이고 세로가 h인 직사각형에서 쓸 수 있는 정사각형의 개수(n)를 일반화시킬 수 있다. 단 w와 h가 서로소인 경우로만 한정한다.

n = w * h - (w + h - 1)

다시 이 큰 사각형을 보자. 빨간 테두리로 그린 사각형의 개수는 4개이다. 놀랍게도 이 4라는 숫자는 가로와 세로의 최대 공약수이다! 작은 사각형의 가로길이와 세로 길이도 이 큰 사각형과 최대공약수로 나타낼 수 있게 되었다.

작은 사각형의 가로 길이 = 전체 사각형의 가로길이 / 최대 공약수

작은 사각형의 세로 길이 = 전체 사각형의 세로 길이 / 최대 공약수

이번에는 가로가 12, 세로가 9인 직사각형에 대해서도 똑같이 계산할 수 있을지 살펴보자.

이 결과도 가로가 (12 / 3 = )4, 세로가 (9 / 3 = ) 3인 직사각형이 3개가 나오는 것으로 위와 똑같이 결과를 얻을 수 있었다.

이 결과와 위에서 얻은 일반화 식을 이용해 전체 사각형에서 쓸 수 있는 사각형의 개수(N)를 구하는 식을 만들 수 있다.

N = w(가로)*h(세로) - (w / g + h / g - 1) * g (g는 w와 h의 최대 공약수)

지금까지의 과정을 토대로 얻은 결과를 코드로 적은 것이 아래의 코드다.

#참고: https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python
from math import gcd

def solution(w,h):
    g = gcd(w, h)
    return w * h - (w // g + h // g - 1) * g

 

아직 수학적으로 사고하는 것에 많이 어색하다. 이 것도 결국 많이 접해보는 것만이 방법이겠지..