백준 17087 숨바꼭질 6

작성일 | In |

Problem : 숨바꼭질 6

유형 : 수학

문제 설명

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

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

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

예제 입력

1
2
3 3
1 7 11

예제 출력

1
2

해결 전략

수빈이와 동생들의 거리를 재본다.

모든 동생들을 찾아야 하므로, 동생들의 거리들중 최대 공약수를 구하면된다.

주의할 점

  • 수빈이의 거리와 동생의 거리를 뺏을때, 음수가 될 수 있으므로 절대값을 이용해 해결한다.

풀이

수빈이와 동생들의 거리를 구한다.

  • 수빈이의 위치 좌표에서 동생들의 위치 좌표를 뺀다.
    • 음수가 될 수 있으므로, 절대값을 취한다.

동생들간의 거리들중 최대 공약수를 찾는다.

  • 모든 동생을 찾아야 하므로, 모든 동생들에게 갈 수 있어야한다.
    • 최대 공약수를 구하면된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;

int n ,subin;
int answer;

void solve() {
    int brother;
    for (int i = 0; i < n; ++i) {
        cin >> brother;
        if (i == 0) answer = abs(subin - brother);
        else {
            answer = gcd(answer, abs(subin - brother));
        }
    }
    cout << answer;
}

void input() {
    cin >> n >> subin;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    input();
    solve();

    return 0;
}

피드백

없음