백준 2981 검문 (JAVA 자바 풀이)

백준 2981 검문 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

 

 

⚔ 입력

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

 

 

📣 출력

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 이때, M은 증가하는 순서이어야 한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

핵심은 M으로 나누면 나머지가 모두 같아진다는 사실에 있다. 

 

이것으로부터 수들 간의 공식을 구할 수 있는데 아래 그림과 같이 나머지 공식을 풀어 쓴 두 수를 빼면 나머지가 같기 때문에 지워지고 곱셈 형식으로 환원되며, 이는 곧 M이 차이의 약수라는 뜻이다. 

 

여러개의 수가 있기 때문에 각각의 약수를 모두 구해서 공통된 것을 골라도 되겠지만, 최대 공약수를 구하고 최대 공약수의 약수를 구하는 것도 같은 이치이다. 

 

곱셉의 특성상 한번 구한 최대 공약수는 또한 다른 수의 반드시 최대 공약수가 되어야 하기 때문에 매번 새로운 계산을 하지 않고 이미 구한 값으로 다음 최대 공약수를 구해줄 수 있다. 

 

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		int numberCounts = Integer.parseInt(bufferedReader.readLine());

		int[] numbers = new int[numberCounts];
		for (int i = 0; i < numberCounts; i++) {
			numbers[i] = Integer.parseInt(bufferedReader.readLine());
		}

		int gcdBtwDifference = Math.abs(numbers[0] - numbers[1]);
		for (int i = 1; i < numberCounts - 1; i++) {
			gcdBtwDifference = gcd(gcdBtwDifference, Math.abs(numbers[i] - numbers[i + 1]));
		}

		System.out.println(commonDivisors(gcdBtwDifference));
	}

	private static StringBuilder commonDivisors(int gcdBtwDifference) {
		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 2; i <= gcdBtwDifference; i++) {
			if (gcdBtwDifference % i == 0) {
				stringBuilder.append(i).append(" ");
			}
		}
		return stringBuilder;
	}

	private static int gcd(int number1, int number2) {
		if (number2 == 0) {
			return number1;
		}
		return gcd(number2, number1 % number2);
	}

	private static int lcm(int number1, int number2) {
		return number1 * number2 / gcd(number1, number2);
	}

	private static int lcm(int number1, int number2, int gcd) {
		return number1 * number2 / gcd;
	}
}