[BaekJoon] 2981 검문

1.  문제 링크

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

2.  문제

요약

• 근처에 보이는 숫자 N개를 종이에 적고, 그 다음 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 1보다 큰 M을 모두 찾으려고 합니다.
• N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 100보다 작거나 같은 종이에 적은 수의 개수 N이 주어지고 두 번째 줄부터 N개의 줄에는 1보다 크거나 같고 1,000,000,000보다 작거나 같은 종이에 적은 수가 하나씩 주어집니다.
  • 같은 수가 두 번 이상 주어지지 않고 M이 하나 이상 존재하는 경우만 입력으로 주어집니다.
• 출력: 첫 번째 줄에 가능한 M을 오름차순으로 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	public int gcd(int a, int b) {
		if(b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
	
	public ArrayList<Integer> getNum(int[] nums) {
		int[] dif = new int[nums.length - 1];
		for(int i = 0; i < nums.length - 1; i++) {
			dif[i] = Math.abs(nums[i] - nums[i + 1]);
		}
		int gcdNum = dif[0];
		for(int i = 1; i < dif.length; i++) {
			gcdNum = gcd(gcdNum, dif[i]);
		}
		ArrayList<Integer> divisor = new ArrayList<Integer>();
		for(int i = 2; i <= gcdNum; i++) {
			if(gcdNum % i == 0) {
				divisor.add(i);
			}
		}
		return divisor;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] nums = new int[num];
		for(int i = 0; i < num; i++) {
			nums[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		ArrayList<Integer> divisor = m.getNum(nums);
		for(int i : divisor) {
			bw.write(i + " ");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 주어진 N개의 수를 $A_1$, $A_2$, $A_3$, ..., $A_N$이라고 가정합니다.
• N개의 수를 M으로 나누었을 때 나머지가 모두 같다고 하였으므로 아래와 같은 식이 생성될 수 있습니다.
  • $A_1$ = $M$ * $s_1$ + $r$
  • $A_2$ = $M$ * $s_2$ + $r$
  • $A_3$ = $M$ * $s_3$ + $r$
  • ....
  • $A_N$ = $M$ * $s_N$ + $r$
• 위 식에서 인접한 2개의 식을 빼주면 아래와 같은 새로운 식이 발생됩니다.
  • $(A_1 - A_2)$ = $M$ * $(s_1 - s_2)$
  • $(A_2 - A_3)$ = $M$ * $(s_2 - s_3)$
  • ...
  • $(A_{N-1} - A_N)$ = $M$ * $(s_{N-1} - s_N)$
• 인접한 2개의 식을 빼서 도출한 식들을 보면 나머지가 없고 등호 왼쪽에 있는 값이 M으로 나누어떨어지는 경우가 됩니다.
• 즉, M은 등호 왼쪽에 있는 값들의 공약수가 된다는 의미가 됩니다.
• 이러한 의미를 이용하여 주어진 N개의 수를 인접한 2개씩 빼준 후에 뺀 값들의 공약수를 찾으면 되는 문제입니다.
• 공약수를 찾을 때, 인접한 2개씩 뺀 수들의 최대공약수를 찾은 후에 그 최대공약수의 약수들을 찾으면 모든 약수들을 찾을 수 있습니다.

1. 주어진 수들에서 인접한 2개씩 빼준 값을 저장할 1차원 배열 dif를 생성하고 인접한 2개씩 빼준 값을 절댓값으로 dif에 넣어줍니다.
2. 인접한 2개씩 빼준 값들의 최대공약수를 나타내는 gcdNum 변수를 생성하고 인접한 2개씩 빼준 값 중 첫 번째 값으로 값을 초기화해줍니다.
3. 인접한 2개씩 빼준 값 중 두 번째 값부터 마지막 값까지 반복문을 돌면서 인접한 2개씩 빼준 값들의 최대공약수를 구합니다.

   1. 이전까지의 최대공약수와 반복문에서의 현재 값 두 값 사이의 최대공약수를 구합니다.

      • 최대공약수를 구할 때는 유클리드 호제법을 이용하여 구합니다.
4. 3번 반복문을 통해 구한 최대공약수의 약수들을 저장할 ArrayList divisor를 생성합니다.
5. M은 1보다 큰 수이기 때문에 2부터 시작하여 구한 최대공약수까지 반복문을 돌면서 만약 구한 최대공약수가 해당 수를 통해 나누어떨어진다면 해당 수를 divisor에 추가합니다.
6. divisor에 수들을 추가할 때 낮은 숫자부터 차례대로 추가해줬기 때문에 이미 오름차순으로 되어있으므로 divisor에 들어있는 수들을 순서대로 출력합니다.