백준 17087. 숨바꼭질 6

숨바꼭질 6

1. 간단 설명

---

문제 이해하는데 약간 시간이 걸렸다

수빈이가 D칸씩 이동할 수 있는데,

모든 동생들의 좌표를 찍어야한다

이동 거리의 최대 혹은 최소값을 구하는 문제가 아니라, 이 D를 어떻게 설정할 것인지를 묻는 문제

예시

3 3
1 7 11

동생 3명, 각 동생의 좌표는 1, 7, 11이고

수빈이의 좌표는 3이다

수빈이와 각 동생들의 거리를 구해보면 각각 2, 4, 8 이다

D칸씩 움직여서 모든 좌표를 찍어야한다면

이 세 거리의 최대공약수인 2를 설정해야 도달할 수 있다

3 81
33 105 57

예제 2번의 수빈이의 좌표 81에서

33, 105, 57에 도달할수 있는 D는

|33-81|, |105-81|, |57-81| 의 gcd인 24이다

2. 문제 분석

---

필요 변수

• 동생 몇명인지 int N (1<= N <= 100,000)
• 수빈이의 좌표 int S (1<= S <= 1,000,000,000)
• 동생들의 좌표 int A (1<= A <= 1,000,000,000)
• 동생들의 좌표를 저장할 벡터 vector<int> v
• 결과값을 저장할 int res
  • S와 A들의 최대공약수이므로 최대 10억을 넘지 않음

알고리즘

1. 동생 몇명인지 N와 수빈이의 좌표 S 입력받기 
2. 각 동생의 좌표를 입력받아, S와의 거리를 저장
3. 만약 동생이 한명이라면, 그 동생과의 거리를 바로 출력 후 종료
4. 동생이 여러명인 경우, 수빈이와 동생간의 거리들의 최대공약수를 계산
5. 출력 후 종료

3. 소스코드

---

#include <iostream>
#include <numeric>
#include <cmath>
#include <vector>

#define MAX 100001

using namespace std;

int N, S;
vector<int> v;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> S;

	// S를 원점으로 두고 각 거리들의 절대값을 저장
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		v.push_back(abs(tmp - S)); 
		// 거리이므로 절대값 사용. 근데 gcd구할거면 상관 없긴함
	}

	if (v.size() == 1) {
		cout << v[0];
		return 0;
	}

	int res = gcd(v[0], v[1]);

	for (int i = 1; i < N; i++) {
		res = gcd(res, v[i]); // numeric 헤더의 gcd 함수 사용
	}

	cout << res;

	return 0;
}

• 벡터를 사용하지 않고 입력을 바로 처리하는 간략화한 버전

#include <iostream>
#include <numeric>
 
using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	int N, S;
	cin >> N >> S;

	int tmp;
	cin >> tmp;

	int res = tmp - S;

	for (int i = 1; i < N; i++){
		cin >> tmp;
		res = gcd(res, tmp-S);
	}

	cout << res;

	return 0;
}

배운점

• 음수의 최대공약수 구하기