[백준_2981번] 검문

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

2981번: 검문

[문제]

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

 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

 

[입력 조건]

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

 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다. 항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_2981 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] arr=new int[n];
		
		for(int i=0;i<n;i++)
			arr[i]=sc.nextInt();
		
		Arrays.sort(arr); // 음수가 되지 않도록 정렬
		
		int gcdVal=arr[1]-arr[0]; // 양수
		
		for(int i=2;i<n;i++)
			// 직전의 최대 공약수와 다음 수(arr[i]-arr[i-1])의 최대공약수를 갱신 
			gcdVal=gcd(gcdVal,arr[i]-arr[i-1]);
		
		// 최대 공약수의 약수들 찾아 출력
		for(int i=2;i<=gcdVal;i++)
			if(gcdVal%i==0)
				System.out.print(i+" ");
	}
	
	// 최대공약수 구하는 함수
	public static int gcd(int a, int b) {
		while(b!=0) {
			int r=a%b;
			
			a=b;
			b=r;
		}
		return a;
	}
}

 

[고찰]

 해당 문제는 다른 사람의 포스팅을 참고하여 해결한 문제이다. 문제 해결 알고리즘은 아래와 같다.

 

                                                              <알고리즘> 

임의의 정수 A1과 A2는 다음과 같이 표현 할 수 있다. A1 = M * a1 + r1, A2 = M * a2 + r2 이 때 나머지가 같아야 하기 때문에 r1과 r2가 같아야 한다는 가정하에  A1에서 A2를 빼면 다음과 같이 만들 수 있다. 

A1 - A2 = M * (a1 - a2) + (r1 - r2) , r1 - r2 = 0 이므로 -> A1 - A2 = M * (a1 - a2)  M 은 (A1 - A2) 의 약수이므로, A1 과 A2 의 공약수가 된다.  
 

 예를 들어, 6 ,34, 38이 주어졌을때 -> 6 / M + r, 34 / M + r, 38 / M + r로 표현할 수 있다. 여기서 r은 모두 같기 때문에 r을 0으로 만들 수 있다면 M을 구힐수 있다. (6 / M + r) - (34 / M + r) 을 풀어서 다시 묶어 표현하면 (6 - 34) / M 이라는 식이 나온다. 그리고 M은 모두 같다는 의미는 앞서 말했듯 6 - 34) / M 라는 식과, (34 - 38) / M 의 M이 같다는 말이고, 다르게 표현하면 M은 (6 - 34)와 (34 - 38)의 공약수라는 의미라는 것. 만약 다른 예제로 17, 34, 24, 52, 39 가 있으면, (17 - 34)와 (34 - 24)와 (24 - 52)와 (52 - 39)의 공약수를 찾으면 된다는 것이다. 즉, 각 배열 (n+1 - n) 값들의 최대 공약수를 찾아 최대 공약수의 약수들을 구하면 정답이다. 

 

포스팅을 보며 이해한 내용을 적은 것이다. 포스팅을 따라가면서 이해하기도 쉽지는 않아 복습해야 할 문제들에 포함시켜 여러번 반복해야겠다고 생각한다.