[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 숨바꼭질 6 (17087)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 숨바꼭질 6 (17087)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이 - 숨바꼭질 6 (17087)

 

---

 

17087번: 숨바꼭질 6

[ 문제 ]

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

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

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

[ 입력 ]

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

[ 출력 ]

가능한 D값의 최댓값을 출력한다.

 

---

[ 코드 ]

#include<iostream>
using namespace std;

// 이 문제는 최대공약수 문제
// 수빈이와 동생들 사이의 모든 거리차이에 대한, 최대공약수를 구하면 된다.

int gcd(int a,int b) {
	if (b == 0)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b); 
		// a<b인 경우 코드를 따로 구현해주지 않아도, 이 과정에서 자리에 맞게 바뀜
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int N; // 동생 N명 (1<=N<=10^5)
	int S; // 현재위치 S (1<=S<=10^9)
	cin >> N >> S;

	int *A = new int[N]; 
	// 동생 N명 위치 -> 거리차이 [동적할당 활용 N개의 공간 마련을 위해]

	for (int i = 0; i < N; i++)
	{
		cin >> A[i]; // 동생 위치
		A[i] = abs(S - A[i]); // 수빈이와의 거리차이
	}


	int result = A[0]; 
	for (int i = 1; i < N; i++)
	{
		result = gcd(result, A[i]);
	}

	cout << result << '\n';

	return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

int gcd(int a, int b) {
	if (b==0)
	{
		return a;
	}
	else
	{
		return gcd(b, a % b);
	}
}

int main() {
	int N, S;
	cin >> N >> S;

	vector <int> arr(N);
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	int result = abs(S-arr[0]);
	for (int i = 1; i < N; i++)
	{
		result = gcd(result, abs(S - arr[i]));
	}

	cout << result;
	return 0;
}

---

* 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :)