[프로그래머스 Lv.2] 멀쩡한 사각형
가로x세로 길이가 주어졌을 때, 직사각형을 반으로 자르면 선이 그어지지 않은 부분의 면적(정사각형의 갯수)를 구해야하는 문제이다.
문제를 처음 보자마자 가로x세로 길이에 따라서 반으로 잘랐을 때 선이 그어지는 부분의 면적의 관계성을 파악하려고 했다.
한참을 고민하다가 결국 구글링을 해보았는데 그 답은 최대공약수라는 것을 알 수 있었다.
[ case 1 ] 최대공약수가 1
최대공약수가 1일 때는 직선은 점을 만나지 않고 무조건 도형을 만난다.
예를 들어 8x5 직사각형일 때 그러하다.
8X5일 때는 12의 정사각형에 선이 그어졌다.
8X3일 때는 10개의 정사각형에 선이 그어졌고
8x7일 때는 14개의 정사각형에 선이 그어졌다.
선이 그어지는 부분의 면적을 구하는 규칙은 w+h-1임을 알 수 있다.
사실 참고한 블로그에서는 이 부분을 선이 그어질 때마다 가로의 갯수와 세로의 갯수만큼 사각형이 갈라지고,
처음에 겹치는 정사각형을 위해 하나를 제외했다고 하는데 사실.. 이해가 잘 안된다.
[ case 2 ] 최대공약수가 1이 아닌 어떤 수!
문제의 테스트케이스에서도 주어진 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발상이 어려워서 그렇지, 규칙만 찾으면 구현은 굉장히 간단하다.
이런 발상은 어떻게 하는걸까... 오늘도 또 코딩테스트에 조져지는 나였다..
다음부터는 좀 더 빨리 최대공약수임을 눈치챌 수 있을거야😭