백준 17087 숨바꼭질 6

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

17087번: 숨바꼭질 6

풀이

최대 공약수 문제입니다!

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

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이 될 때의 앞의 원소 값이 최대 공약수가 됩니다. 

 

소스 코드

#include <iostream>
#include <vector>
using namespace std;
 
long long gcd(int a, int b) {
    if (b == 0) return 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);
}

개발환경 : Visual Studio 2019

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