최대 공약수를 구하고, 서로소를 나누는 선분으로 사라지는 사각형의 갯수를 구하는 문제.
알고리즘보단 수학적 개념을 요하는 것 같다.
파이썬과 자바의 풀이가 대동소이하므로 한번에 올리고 개념적인 측면으로 접근하도록 하겠다.
class Solution {
public long solution(int w, int h) {
long max, min, temp, y, x;
if (w > h) {
max = w;
min = h;
} else {
max = h;
min = w;
}
while (min != 0) {
temp = max % min;
max = min;
min = temp;
}
y = h / max;
x = w / max;
return (long)w * (long)h - (y + x - 1) * max;
}
}
def solution(w,h):
GCF, check = max(w, h), min(w, h)
while check:
GCF, check = check, GCF % check
y, x = h // GCF, w // GCF
return w * h - (y + x - 1) * GCF
주어진 w, h에서 최대공약수를 구한 후 서로소 형태로 만든 뒤에 선에 의해 사라지는 사각형의 갯수를 구했다.
유클리드 호제법
을 사용했다.
A와 B가 있을 때 A, B
의 최대공약수는 B, A % B
의 최대공약수와 같다는 공식이다.
A와 B는 자연수, A >= B로 가정.
A = ax
, B = bx
로 두겠다. x는 A와 B의 최대공약수이다.
r = A % B
로 하면 A = By + r
로도 볼 수 있다. y는 0 이상의 임의의 수이다.
따라서 A = By + r = bxy + r = ax
가 성립한다.
이 때 r을 기준으로 이항시킨다면, r = ax - bxy = x(a - by)
가 된다.
따라서 r 또한 x를 약수로 지니고 있다는 뜻이 된다.
그러므로 A
와 B
의 최대공약수는 x
이며, B
와 r (= A % B)
의 최대공약수 또한 x
이다.
이 때, r이 0이라면 A와 B의 최대공약수는 B가 되므로(A = Bx) 우리는 A, B -> B, r
형태를 반복하다가 r이 0이 되는 순간을 잡아내면 된다.
서로소 상태의 사각형에서 선을 그었을 때, 선이 침범하는 사각형의 갯수를 세면 된다.. 지만 어떻게 수학적으로 나타내야 할 지 불분명하다. 따라서 2개의 증명으로 갯수를 구해보겠다.
서로소로 이루어진 사각형에 대각선을 긋는다는 건, 가로축에서 선 하나, 세로축에서 선 하나를 그은 후 겹친 부분의 갯수를 제거해주면 된다.
더 자세히 알아보자.
해당하는 5 * 3
짜리 사각형을 생각해보자.
우선 가로 축으로, 선에 의해 침범된 사각형을 지워보도록 하겠다.
가로 축에서 선이 시작되는 부분을 기준으로, 5개가 지워지는 것을 확인할 수 있다.
하지만, 세로 축을 기준으로 지워지는 사각형들 또한 존재한다. 해당하는 것들도 지워보도록 하겠다.
해당하는 3개의 사각형이 지워진다.
사라지는 사각형을 모두 표기해보자.
가로 축 기준으로 5개의 사각형이, 세로 축 기준으로 3개의 사각형이 지워졌었다.
맨 처음 겹친 0, 0
을 중복제거해 주면, 5 + 3 - 1
개의 사각형이 지워졌다.
..이게 맞나 싶을 거다. 더 확실한 증명이 있어야하지 않겠는가?
이번엔 동시에 2개가 사라질 때를 기준으로 보겠다.
가로를 b, 세로를 a로 두고 b >= a로 한다면 해당 선은 y = a/b * x
로 볼 수 있다.
차원적 증명으로, 가로 기준 각각 칸 하나씩은 지워지는 것을 확인했으니 우선 b개의 사각형은 지워진다.
이 때, 동시에 2개가 지워지는 영역은 y = a/b * x
에서 y가 1->2, 2->3, ... 처럼 낮은 값에서 높은 값으로 바뀌는 구간에 일어난다.
x가 0 -> 1일 때 y는 0 ~ 0.6
x가 1 -> 2일 때 y는 0.6 ~ 1.2 -> 값 침범으로 2개
x가 2 -> 3일 때 y는 1.2 ~ 1.8
x가 3 -> 4일 때 y는 1.8 ~ 2.4 -> 값 침범으로 2개
x가 4 -> 5일 때 y는 2.4 ~ 3.0
이 때, 낮은 값에서 높은 값으로 바뀌는 구간은 0 -> 1, 1 -> 2, ... , a-2 -> a-1, a-1 - > a
로 총 a - 1
개이다.
따라서 지워지는 사각형은 a + b - 1
개가 된다.
사각형이 지워지는 패턴은 최대공약수만큼 반복되므로, 모든 사각형의 갯수 w * h
에서 a + b - 1 * 최대공약수
를 곱해준 것과 같다.
따라서 최종 식은 w * h - (a + b - 1) * 최대공약수
가 된다.