백준 17087 c++ 숨바꼭질 6

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

17087번: 숨바꼭질 6

#include <iostream>
using namespace std;

long long gcd(long long a, long long b)//최대공약수 구하기
{
	if (b > a)
	{
		long long tmp = a;
		a = b;
		b = tmp;
	}
	if (b == 0)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}

int main()
{
	long long num;//동생의 수
	cin >> num;
	long long S;//본인의 위치
	cin >> S;
	long long position[100001];//동생들의 위치
	if (num == 1)//동생이 한명일경우
	{
		cin >> position[0];//입력받은 동생의 위치 - 본인 위치
		cout << abs(position[0] - S);//abs = 절댓값 구하는 함수
	}
	else if (num == 2)//동생의 수가 2명일 경우
	{
		cin >> position[0];
		cin >> position[1];//동생 위치-본인위치 의 최대 공약수를 구함
		cout << gcd(abs(position[0] - S), abs(position[1] - S));
	}
	else//동생이 3명 이상일 경우
	{
		for (int i = 0; i < num; i++)
		{
			cin >> position[i];//동생들의 위치를 채워넣고
			position[i] = abs(position[i] - S);//거기에 본인의 위치를 빼줌
		}
		long long result = gcd(position[0], position[1]);
		for (int i = 2; i < num; i++)//동생위치에서 본인 위치 뺀 값의 최대공약수
		{
			result = gcd(result, position[i]);
		}
		cout << result;
	}
}

이 문제에서 D값은 (동생들의 위치 - 본인의 위치) 즉 거리이기 때문에 절댓값을 씌워줘야한다.

그리고 그 값들의 최대 공약수가 D값이 된다.

 

최대공약수 구하기 - https://mun-coding.tistory.com/31