이번 문제는 아래 링크에서 풀어볼 수 있습니다.
17087번: 숨바꼭질 6
수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이
www.acmicpc.net
문제
수빈이는 동생 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값의 최댓값을 출력한다.
예제 입력 1
3 3
1 7 11
예제 출력 1
2
예제 입력 2
3 81
33 105 57
예제 출력 2
24
예제 입력 3
1 1
1000000000
예제 출력 3
999999999정답 코드
문제 풀이
주어진 수빈이의 현재 위치 s와 동생의 위치들의 최대공약수를 유클리드 호제법을 통해 구해내면 되는 문제이다. 왜 최대공약수를 구해야 하는지 예제 입력 1을 토대로 설명하겠다.
3 3
1 7 11
1 - 3 = 2
7 - 3 = 4
11 - 3 = 8
위와 같이 동생의 위치와 수빈이의 위치의 차가 2의 배수임을 볼 수 있다. 즉 결괏값들의 최대공약수는 '2'가 되는 것이고 수빈이는 한 번에 2씩 움직여 모든 동생을 찾을 수 있다.
함께 보기
[Baekjoon] 9613 GCD 합(자바스크립트/NodeJs)
이번 문제는 아래 링크에서 풀어볼 수 있습니다. 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의
gdk01.tistory.com
[Baekjoon] 2609 최대공약수와 최소공배수(파이썬/자바스크립트/NodeJS)
이번 문제는 아래 링크에서 풀어볼 수 있습니다. 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출
gdk01.tistory.com
https://gigibean.tistory.com/29
'👩💻 Programming > Coding Test 문제 풀이' 카테고리의 다른 글
| [Baekjoon] 1212 8진수 2진수(자바스크립트/NodeJs) (1) | 2023.01.09 |
|---|---|
| [Baekjoon] 1373 2진수 8진수(자바스크립트/NodeJs) (0) | 2023.01.09 |
| [Baekjoon] 2004 조합 0의 개수(자바스크립트/NodeJs) (0) | 2023.01.03 |
| [Baekjoon] 1676 팩토리얼 0의 개수(파이썬/자바스크립트/NodeJs) (0) | 2023.01.02 |
| [Baekjoon] 10872 팩토리얼(파이썬/자바스크립트/NodeJS) (0) | 2023.01.02 |
댓글