문제 링크

문제 간단 해석

최대 공약수를 구하고, 서로소를 나누는 선분으로 사라지는 사각형의 갯수를 구하는 문제.
알고리즘보단 수학적 개념을 요하는 것 같다.
파이썬과 자바의 풀이가 대동소이하므로 한번에 올리고 개념적인 측면으로 접근하도록 하겠다.

Java

풀이 코드

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;
    }
}

Python

풀이 코드

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) * 최대공약수 가 된다.