[정수론] 백준과 함께 하는 정수론 - 3

[BOJ 2485번 가로수]

임의의 간격으로 배열 되어있는 가로수들이 모두 같은 간격이 되도록 가로수를 새로 심어야 하는 최소수를 구하는 문제이다.

1 3 7 13 위치에 있다면 1 3 5 7 9 11 13 과 같이 3그루를 심어주면 된다.

심는 가로수가 최소가 되려면 같은 간격이 되었을 때, 그 간격이 최대여야 한다. 즉, 최대공약수 를 구하는 문제이다.

모든 간격들의 최대공약수가 같은 간격이 되었을 때의 간격이 되는 것이고, 심어야 하는 가로수의 수는 간격들을 최대공약수로 나눈 값에 1을 빼준 값을 계속해서 더해가면 구할 수 있다.

그렇다면 최대공약수는 어떻게 구할까?

수학 시간에 최대공약수를 구하는 방법으로는 크게

• 서로소가 나올 때까지 공약수로 나누기
• 소인수 분해 후 공통인 것 중 지수가 작은 것 찾기

이렇게 2가지로 배웠을 것이다.

하지만 위의 두 방식은 코드로 구현 시 비교적 무거운 코드 (시간이 오래 걸리는)가 나올 것이다.

그렇기에 보통 PS 에서는 다른 방식으로 GCD(최대공약수)를 구하는데, 유클리드 호제법 이 그 방식이다. 아래에서 작동 방식을 보자.

a, b 의 GCD를 구하는 과정이다.
a를 b로 나누었을때

• 나누어 떨어지면 b가 GCD이다.
• 나누어 떨어지지 않으면 b와 a를 b로 나눈 나머지에 대해 다시 위 작업을 실행한다.

이 방식이 최대공약수를 구하는지 증명해보도록 하자.

증명

---

$a, b \in Z$이고 $a$를 $b$로 나눈 나머지를 $r$이라고 하자. ($a\ge b$)

$a=bQ+r$ 과 같이 놓을 수 있다. (정수 $Q, r$은 유일하다.)

$gcd(a, b)=k$ 라고 하자. $a=k\alpha, b=k\beta$ 로 놓을 수 있다. 최대공약수의 정의에 따라 $\alpha$와 $\beta$는 서로소이다.

$a=bQ+r$ -> $k\alpha =k\beta Q+r$

$k(\alpha -\beta Q)=r\ \therefore k|r$

$r=kx$ 라고 하자. $\beta$, $x$가 서로소라면, $b$와 $r$의 최대공약수 또한 $k$이다. 서로소가 아니라면, $\alpha$와 $\beta$가 서로소라는 것에 모순이 생긴다. -> 결국 $b$와 $r$의 최대공약수가 $k$라는 것이다.

---

유클리드 호제법을 통해 최대공약수를 구하는 과정이 정당함을 보였으니 아래의 코드로 최대공약수를 구하면 된다.

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

유클리드 호제법의 시간복잡도는 $O(logN)$ 이다.
$a_1=b_1Q+r_1$
$a_2(=b_1)=b_2(=r_1)Q+r_2$
...
이를 계속해가는 과정에서 $b$는 2배 이상 감소하며, $a$는 $b$에 종속이기에 위의 시간복잡도를 갖는다.