Suhwanc

문제 링크 : https://www.acmicpc.net/problem/17087

 

17087번: 숨바꼭질 6

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다. 모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

www.acmicpc.net

풀이

최대 공약수 문제입니다!

수빈이와 동생의 위치 차이를

v1,v2,...,vn 이라고 하면, 모든 동생을 찾기 위한 D의 값은 모든 v의 최대 공약수이어야 합니다.

따라서 이 문제는 모든 v의 최대 공약수 찾기 문제로 바꿀 수 있습니다!

참고로 최대공약수는 유클리드 호제법으로 구할 수 있으며

a,b(a>b)의 최대공약수를 구하고자 하면

gcd(a,b) = gcd(b, a%b)

gcd(b,r) = gcd(r, b%r) 

...

로 뒤에 있는 원소값이 0이 될 때의 앞의 원소 값이 최대 공약수가 됩니다. 

 

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
 
long long gcd(int a, int b) {
    if (b == 0return a;
    return gcd(b, a % b);
}
 
int main()
{
    int n; scanf("%d"&n);
    long long s; scanf("%lld"&s);
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%lld"&a[i]);
    }
    for (int i = 0; i < n; i++) { //위치의 차이 구하기
        if (s > a[i]) a[i] = s - a[i];
        else a[i] = a[i] - s;
    }
    long long ans = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] >= ans) ans = gcd(a[i], ans);
        else ans = gcd(ans, a[i]);
    }
    printf("%lld", ans);
}
cs

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 17404 RGB 거리 2  (0) 2020.01.16
백준 1309번 동물원  (0) 2020.01.16
백준 17299번 오등큰수  (0) 2020.01.16
백준 17298번 오큰수  (0) 2020.01.16
백준 16194번 카드 구매하기 2  (0) 2020.01.14