[C++] 백준 17087번 : 숨바꼭질 6 (S1)

#문제

www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

#풀이 & 학습한 내용

동생들의 각각의 위치에서 수빈이의 위치를 뺀 값들의 최대공약수(GCD)를 구하는 문제이다. 유클리드 호제법을 이용해 GCD를 구하고, GCD(a,b,c)=GCD(GCD(a,b),c)임을 통해 순차적으로 계산한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
long long gcd(long long a, long long b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}
 
int main(void) {
    long long N, S;
    cin >> N >> S;
 
    long long p,k;
    cin >> p;
    p = abs(p - S);
    N--;
 
    while (N--) {
        cin >> k;
        p = gcd(p, abs(k-S));
    }
    cout << p << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_17087.cpp

HoYoungChun/BOJ_algorithm