(Python/파이썬) - 백준(BOJ) 17087번 : 숨바꼭질 6

https://www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

---

• 문제 : 

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

 

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

 

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

 

---

• 풀이 :

최대공약수를 찾는 문제입니다. 

 

문제분류에 유클리드 호제법이 들어가있는데

유클리드 호제법이란 최대공약수를 찾기 위한 방법으로 간단히 설명하면

 

56과 35가 있다고 가정할 때, 

 

1. 56은 35로 나누어 떨어지지 않으므로 56을 35로 나눈 나머지를 구함 -> 21

 

2. 35는 21로 나누어 떨어지지 않으므로 35를 21로 나눈 나머지를 구함 -> 14

 

3. 21은 14로 나누어 떨어지지 않으므로 21을 14로 나눈 나머지를 구함 -> 7

 

4. 14는 7로 나누어 떨어지므로 56과 35의 최대공약수는 7

 

이런 흐름의 알고리즘입니다.

기본 코드는 아래와 같습니다.

int gcd(int a, int b)
{
    while (b > 0)
    {
        int tmp = a;
        a = b;
        b = tmp%b;
    }
    return a;
}

 

물론 Python에는 math 모듈의 gcd 메소드를 사용하면 함수를 굳이 구현하지 않아도 됩니다.

 

 

문제 해결 알고리즘의 흐름입니다.

 

1. 수빈이와 N명의 동생들 사이의 거리들의 최대공약수를 구해야 하므로 입력받은 t (동생들의 위치)를 Linear Search로 탐색합니다.

 

2. gcd값을 누적하기 위해 이전 값의 gcd값을 저장하고 다음 값과 gcd연산을 수행합니다. 

 

  ex)  56, 35, 14가 있다면 56과 35의 최대공약수는 7이고 7과 14의 최대공약수는 7이므로 세 수의 최대공약수는 7이다.

 

3. 마지막 gcd 연산의 값이 모든 값의 최대공약수이므로 이를 출력하면 됩니다.

 

 

 

---

• 소스코드 : 

from math import gcd
N,S = map(int,input().split())
t = list(map(int,input().split()))
g = abs(t[0]-S) 
# 수빈이의 위치와 동생의 위치 차이의 최대공약수를 구해야함. 
for i in t[1:]:
    g = gcd(abs(i-S),g)
print(g)