[프로그래머스/파이썬] 멀쩡한 사각형

문제 접근 방법이 매우매우 수학적이라서

신선하기도 하고... 이걸 못푼 것에 대해 현타도 와서...^^

충격받은 마음으로 문제 접근 방법을 정리해보고자 한다.

 

문제는 다음 링크를 클릭하면 확인할 수 있다.

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

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

 

첫 번째 접근 방법

import math
def solution(w,h):
    total = w * h
    # 가로: w, 세로: h
    # 가운데를 지나는 직선 함수
    def slope(x):
        return (h*x) / w
    
    minus = 0
    # 가로는 01, 12, 23, 34, ... w-1,w
    for i in range(w):
        left = slope(i)
        right = slope(i+1)
        minus += math.floor(right-left)+1
    return total - minus

 

처음에는 좌표평면상에 사각형이 놓여있다고 생각하고

직선을 구해서 y값을 구하는 방식으로 접근하였다.

가로길이가 w일 경우, (0,1), (1,2),(2,3) ... (w-1,w) 로 접근하면서 각 x값에 대응하는 y값을 구해 차를 구한 뒤, 1을 더해주었다. (minus)

그리고 총 1x1 직사각형의 개수(w*h)에서 minus 값을 빼주었다.

하지만 결과는 1개를 제외한 모든 테스트케이스가 틀렸고, 시간초과가 나는 것들도 있었다.

w와 h가 1억 이하의 자연수이기 때문에 최악의 경우 for문을 통해 1억번의 연산을 하게 되기 때문인 것 같다.

 

두 번째 접근 방법 (정답)

시간초과가 나지 않기 위해서 for문을 쓰지 않아야 한다고 생각하였다.

근데 도저히 답을 모르겠어서 구글링하였고, 

정말 정말 간단한 코드로 풀린다는 것에 큰 충격을 받았다

 

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

 

 

실화인가요???

도대체 갑자기 gcd가 왜 나온건지.. 이해할 수 없었다.

 

그림을 그려서 생각해보았다.

 

예제와 같이 w가 8이고 h가 12인 경우, 다음과 같은 직선이 그려진다.

그리고, 이 직선은 4개의 꼭짓점을 지난다. (2,3), (4,6), (6,9), (8,12)

이 꼭짓점을 기준으로 지나가는 사각형을 보았을 때, 겹치는 사각형들이 중복됨을 볼 수 있다. (핑크색 라인)

2x3 사각형일 경우 지나가는 사각형의 개수는 2+3-1이 된다.

4x6 사각형일 경우 지나가는 사각형의 개수는 4+6-2가 된다.

6x9 사각형일 경우 지나가는 사각형의 개수는 6+9-3이 된다.

8x12 사각형일 경우 지나가는 사각형의 개수는 8+12-4가 된다.

 

즉, WxH 사각형일 경우 지나가는 사각형의 개수는 W+H-gcd(W,H)가 됨을 알 수 있다.

따라서 코드가 위와 같이 아주.. 간결하게 나온다!