2981번 - 검문
n개의 수를 입력받아서 m으로 나눈 나머지에 대해 모든 n개의 나머지가 같게 하는 m들을 찾는 문제입니다.
어떤수 x를 y로 나누었을 때의 나머지가 n이라 하면 x = y * z + n으로 표현할 수 있으므로(z는 임의의 자연수)
저는 우선 입력받은 수들을 배열로 저장한 뒤, 오름차순 정렬을 한 것을 x0, x1, ..., xn이라 두었습니다.
그리고 나누는 수 m에 대해 모두 나머지가 n을 가진다면 가장 큰 수 xn과 가장 작은 수 x0에 대해
(xn - x0) = m(zn - z0) 을 얻을 수 있고, (xn - x0)는 단순한 뺄셈이므로 쉽게 구할 수 있습니다.
따라서 나머지가 같게 하는 수 m은 (xn - x0)의 약수가 됨을 알 수 있습니다. (임의의 수 z와 곱셈을 하여 (xn - x0)이 되므로)
1로 나누는 경우는 제외하므로 m에 1은 포함될 수 없으므로
2 <= m <= (xn - x0) 을 만족하는 (xn - x0)의 약수를 찾는 문제로 생각할 수 있다.
여기까지가 제 논리입니다.
하지만 실제로 코딩을 하고 계산을 해보니 18%에서 오답처리가 나는데 도저히 그 이유를 할 수 없습니다.
코딩 선배님들의 조언 부탁드리겠습니다.
dividers 함수에서 num이 9이면 3이 두번 추가될것같습니다
이런 정말 부끄러운 기초적인 실수였네요 3587jjh님 감사합니다!
와 다른분 힌트보고 풀긴 했는데 왜 input value간에 차이의 최대공약수를 구하는지 몰라서 이것저것 찾아보다 이글보고 뽝 이해했네요
자세한 설명 감사합니다 : )
큰 도움이 됐습니다.
댓글을 작성하려면 로그인해야 합니다.
aaadddggg 6년 전 13
n개의 수를 입력받아서 m으로 나눈 나머지에 대해 모든 n개의 나머지가 같게 하는 m들을 찾는 문제입니다.
어떤수 x를 y로 나누었을 때의 나머지가 n이라 하면 x = y * z + n으로 표현할 수 있으므로(z는 임의의 자연수)
저는 우선 입력받은 수들을 배열로 저장한 뒤, 오름차순 정렬을 한 것을 x0, x1, ..., xn이라 두었습니다.
그리고 나누는 수 m에 대해 모두 나머지가 n을 가진다면 가장 큰 수 xn과 가장 작은 수 x0에 대해
(xn - x0) = m(zn - z0) 을 얻을 수 있고, (xn - x0)는 단순한 뺄셈이므로 쉽게 구할 수 있습니다.
따라서 나머지가 같게 하는 수 m은 (xn - x0)의 약수가 됨을 알 수 있습니다. (임의의 수 z와 곱셈을 하여 (xn - x0)이 되므로)
1로 나누는 경우는 제외하므로 m에 1은 포함될 수 없으므로
2 <= m <= (xn - x0) 을 만족하는 (xn - x0)의 약수를 찾는 문제로 생각할 수 있다.
여기까지가 제 논리입니다.
하지만 실제로 코딩을 하고 계산을 해보니 18%에서 오답처리가 나는데 도저히 그 이유를 할 수 없습니다.
코딩 선배님들의 조언 부탁드리겠습니다.