[프로그래머스 Lv.2] 멀쩡한 사각형

프로그래머스 Lv2 멀쩡한 사각형

가로x세로 길이가 주어졌을 때, 직사각형을 반으로 자르면 선이 그어지지 않은 부분의 면적(정사각형의 갯수)를 구해야하는 문제이다.

문제를 처음 보자마자 가로x세로 길이에 따라서 반으로 잘랐을 때 선이 그어지는 부분의 면적의 관계성을 파악하려고 했다.

한참을 고민하다가 결국 구글링을 해보았는데 그 답은 최대공약수라는 것을 알 수 있었다.

👉🏻참고한 블로그

 

[ case 1 ] 최대공약수가 1

최대공약수가 1일 때는 직선은 점을 만나지 않고 무조건 도형을 만난다.

예를 들어 8x5 직사각형일 때 그러하다.

8x5 직사각형 예시

8X5일 때는 12의 정사각형에 선이 그어졌다.

 

8x3 직사각형 예시

8X3일 때는 10개의 정사각형에 선이 그어졌고

 

8x7 직사각형 예시

8x7일 때는 14개의 정사각형에 선이 그어졌다.

선이 그어지는 부분의 면적을 구하는 규칙은 w+h-1임을 알 수 있다.

사실 참고한 블로그에서는 이 부분을 선이 그어질 때마다 가로의 갯수와 세로의 갯수만큼 사각형이 갈라지고,

처음에 겹치는 정사각형을 위해 하나를 제외했다고 하는데 사실.. 이해가 잘 안된다.

 

[ case 2 ] 최대공약수가 1이 아닌 어떤 수!

8x12 직사각형 예시

문제의 테스트케이스에서도 주어진 8x12 직사각형이다.

이때, 대각선은 3개의 점을 만나고 점을 만나는 시점 전후로 똑같은 양상이 4번 반복된다.

8 = 2^3, 12 = 2^2x3 으로 최대공약수는 2^2인 4다.

딱 최대공약수만큼 반복되는 꼴이다.

그렇다면 이 문제는 2x3의 직사각형 문제가 4번 반복되는 형태라고 보면 되겠다.

 

선이 그어지는 부분을 수식화하면 다음과 같다.

g = W와 H의 최대공약수

(W//g+H//g-1) * g = W + H - g

 

각각 케이스에 맞게 구해진 선이 그어지는 면적을 전체 면적에서 빼주면 답이 된다.

---

from math import gcd
def solution(w,h):
    
    lined_space = 0   # 선이 그어진 면적
    g = gcd(w,h)      # 다음과 같이 최소공배수를 구할 수 있다.
    
    if g == 1:
        lined_space = w+h-1
    else:
        lined_space = w+h-g
    
    answer = w*h - lined_space
    return answer

발상이 어려워서 그렇지, 규칙만 찾으면 구현은 굉장히 간단하다.

 

---

이런 발상은 어떻게 하는걸까... 오늘도 또 코딩테스트에 조져지는 나였다..

다음부터는 좀 더 빨리 최대공약수임을 눈치챌 수 있을거야😭