백준 17087 숨바꼭질 6 질문드립니다.

Question

#include #include int compare(const void *arr1, const void *arr2) { if (*(int *)arr1 < *(int *)arr2) { return 1; } else { return -1; } } int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a%b); } } int main() { int n, s, arr[100003] = {0}, res[100002] = {0}, min = 1000000005; scanf("%d %d", &n, &s); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } arr[n] = s; qsort(arr, n + 1, sizeof(int), compare); for (int i = 0; i < n; i++) { res[i] = arr[i] - arr[i + 1]; } qsort(res, n, sizeof(int), compare); for (int i = 0; i < n - 1; i++) { if (min > gcd(res[i], res[i + 1])) { min = gcd(res[i], res[i + 1]); } } if (n == 1) { min = res[0]; } printf("%d", min); return 0; }안녕하세요 백준 문제를 풀다 모르는 게 있어 질문드립니다.백준 질문게시판에도 올려보고 올라와 있는 반례나 테스트케이스를 넣어 정답이 나오는데도 틀렸다고 나오네요.문제를 적어드리면 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.첫째 줄에 N(1 ≤ N ≤ 10^5)과 S(1 ≤ S ≤ 10^9)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 10^9)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.즉 수빈이의 위치와 동생 위치의 거리를 구해 그것의 가장 작은 최대공약수를 구하는 문제 입니다.저는 수빈이의 위치를 동생들의 위치와 한 배열로 놓고 정렬한 후 각 배열 사이의 거리의 최대공약수를 구하였습니다.하지만 정답처리된 다른 사람들의 코드를 보니 수빈이와 각 동생들 위치 차이의 최대공약수를 구했습니다.제가 잘못 푼 것일까요? 아니면 다른 틀린 부분이나 착각한 부분이 있을까요?조언, 지적, 피드백 부탁드립니다.

ColoColo · Accepted Answer

재밌네요. 새로운 접근방식에, 이 방식도 될거 같은데 안된다는게 또 재밌네요.일단 아래 입력이 반례가 될거 같네요.3 14 45 30 20본문의 코드로 위 입력을 처리 할 경우 2가 나오지만 정답은 1입니다. 이유는 한번 생각해 보시고.. 잘 정리 되면 저도 한번 알려주세요ㅎ

백준 17087 숨바꼭질 6 질문드립니다.

1개의 답변

기타 목록