[백준] 2981번 검문 javaScript

yeong·2022년 5월 9일
0

알고리즘

목록 보기
5/5

문제 :

https://www.acmicpc.net/problem/2981

문제 이해

: n개의 데이터가 주어질 때 n개의 원소들을 M으로 나누었을때 나머지가 모두 동일한 M을 구하는 문제이다.
M은 1보다 커야하며, 가능한 M을 모두 찾아야한다.

문제 접근

사실 for문을 모두 돌리면 해결이 가능할 것 같았다. 그러나 주어진 N의 범위가 천만을 넘어가므로 브루스포트 알고리즘을 적용하면 당연히 시간초과가 발생한다ㅠㅠ..
오래 고민해보아도 풀리지않아 여기저기 구글링을 하면서 참고를 하며 문제를 풀었다. 사실 문제의 풀이는 간단했으나 이해하는데 조금 어려움이 있었다.

주어진 N개의 원소는 M으로 나누었을때 모두 같은 나머지를 갖는다는 점을 주목하면 조금 더 이해가 잘 될 것 같다.
주어진 입력 원소들의 배열을 nums라고 했을때 nums[i]는 m에대해
num[i] = k_i M + r
num[i+1] = k_i+1
M +r
num[i+2] = k_i+2 * M + r
...

와 같은 식이 만들어진다.
그리고 나머지가 동일하므로 r을 없애기 위해 각각의 식을 빼면
num[i+1] - num[i] = ( k_i+1 - k_i ) M
num[i+2] - num[i+1] = ( k_i+2 - k_i+1 )
M

이 된다.
여기서 M이 num[i+1] - num[i]num[i+2] - num[i+1] 의 공약수라는 것을 알 수 있다.
즉 M은 원소 num[1]-num[0] , num[2]-num[1]... num[n-1]-num[n] 들의 공약수이다.

이러한 원리를 바탕으로 각 원소들을 순회하면서 공약수들을 구하면 되는데 공약수는 최대공약수의 약수이므로, 최대공약수를 구한 후 해당 숫자의 약수를 구하는것이 제일 간단하다.

또한 주의할 것은 num[i+1]-num[i] ,num[i+2]-num[i+1]뿐만 아니라 모든 원소들 사이 공통된 약수를 구해야하므로 먼저 가장 앞에 위치한 원소들의 최대공약수를 구한후, 해당 최대공약수와 다음 원소들(차감값) 사이의 최대공약수를 구하는 방식으로 진행해야한다.

구현 코드는 아래와 같다.

const fs = require("fs");
const file = "/dev/stdin" ;
const input = fs.readFileSync(file).toString().trim().split("\n");

input.shift();
const numbers = input.map((x) => +x).sort((a, b) => a - b);
let answer = [];
let gcd = numbers[1] - numbers[0];
for (let i = 1; i < numbers.length - 1; i++) {
  gcd = getGcd(numbers[i + 1] - numbers[i], gcd);
}
function getGcd(a, b) {
  while (b > 1) {
    if (a % b === 0) return b;
    else {
      let temp = b;
      b = a % b;
      a = temp;
      console.log(a, b);
    }
  }
  return b;
}
for (let i = 2; i <= gcd; i++) {
  if (gcd % i === 0) answer.push(i);
}
console.log(answer.join(" "));

최대공약수의 약수를 구하는 파트에서 조금 더 효율적인 방법이 있을것 같아 이부분을 추후 개선할 예정이다.

🥲아직 공부을 하며 기록한 블로그입니다! 잘못된 내용이 있다면 편하게 지적부탁드립니다.

ref:
이해하는데 큰 도움이 된 블로그
백준 2981

profile
안녕하세요!

0개의 댓글