최대공약수 (2) 썸네일형 리스트형 17087 백준, 숨바꼭질 6 문제 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다. 출력 가능한 D값의 최댓값을 출력한다. 예제 입력 1 3 3 1 7 11 예제 출력 1 2 예제 입력 2 3 81 .. GCD 알고리즘 GCD(Greatest Common Divisor), 즉 최대 공약수를 구하는 방법에 대해 한 번 알아보고자 한다. 최대 공약수를 구하는 방법은 우리가 이미 초등학교, 중학교 때 배우기는 하였다. 두 수에 대해서 소수(Primary Number)를 나누어 주어 서로소로 만든 후, 나누어주었던 소수 집합을 모두 모아 곱해주면 그게 바로 최대 공약수였다. 그러나 이 방식을 컴퓨터에서 구현하기에는 아름답지 못한 방법이다. 우선 나누어주는 수가 소수인지 판단하는 데 시간을 소모하고, 두 수가 모두 해당 소수로 나누어지는 지 판단해야 한다. 이런 방식은 잠시 뒤로 밀어두고 우리는 유클리드 호제법을 이용하여 GCD를 구하고자 한다. 유클리드 호제법의 가장 기본적이고 핵심적인 부분을 꼽자면 A, B라는 두 수에 대해.. 이전 1 다음
