[백준] 단계별로 풀어보기(단계:17,정수론 및 조합론,JAVA)2981번, 검문

문제 링크

2981번: 검문

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에서 규칙에 대한 알고리즘을 살펴보면 전에

어떤 수를 표현할 때 나누고 나머지로 표현한다면N = n*a + r(N : 수, n: 나누는 값, a: 나눈후 값, r : 나머지)22 = 4*5 + 2 (22를 4로 나누는 형태로 나태낸 값)

 

문제에서는 모든 숫자의 나누었을 때 나머지가 모두 같은 값을 구하는 것으로 식으로 표현하면

N₁ = n * a₁ + r₁

N₂ = n * a₂ + r₂

나머지는 같다(r₁ = r₂)

N₁ - N₂ = n(a₁ - a₂)

위에 식을 보고 알수 있는 내용은 N₁ - N₂의 공약수는 n이라는 것입니다.

예제 입력1에서 6과 34를 적용시키면34-6 = n(a₁ - a₂) => 28 = n(a₁ - a₂) n이 될 수 있는 값은 1, 2, 4, 7, 28으로 6과 34사이에 나머지가 같고 올 수 있는 값이다.

모든 수의 나머지가 같아야 하기 때문에 위 수에서 가장 큰 수와 다음 뺀 것을 구하는 것을 반복해야 합니다.

그래서 n이 될 수 있는 가장 큰 수로 최대 공약수로 구하는 유클리드 호제법을 사용하였습니다.

예제 입력 1로 살펴보며자면34-6와 38-34에 최대 공약수를 구합니다.

28과 4에 최대 공약수는 4가 됩니다.4가 된다는 것은 4의 약수들도 모두 나누었을 때 나머지가 같다는 것을 의미합니다.그래서 출력값이 될 수 있는 값은 1, 2, 4인데 조건에 2보다 큰 것으로 시작하기 때문에 2, 4가 출력됩니다.

 

여기서 입력값을 배열에 저장해놓고 오름차순으로 정렬하였습니다.

이유는 입력값은 정렬이 되어있지 않기 때문에 공약수가 나오면 양수여야 하는데 음수가 나올 수 있기 때문에

sqrt()를 통해 절대값을 취하던가 아니면 오름차순으로 정렬해야 하는데 저는 오름차순으로 정렬하는 방향으로 작성하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• Arrays.sort를 이용하여 배열을 오름차순으로 정렬하였습니다.
• 최대 공약수 구하는 함수 GCD를 만들었습니다.(유클리드 호제법)
• for문을 통하여 위에 알고리즘을 이용하여 GCD 함수를 사용하여 최대 공약수를 구하였습니다.
• for문을 이용하여 최대 공약수의 약수들을 sb에 저장하였습니다.
• BufferedWriter을 사용하여 sb를 출력하였습니다.

• GCD는 유클리드 호제법을 이용하여 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int index;	//숫자의 개수
	static int[] num;	//숫자 저장 배열
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	//BufferedWriter를 통해 결과 값 출력
        //------------입력값 저장 및 배열 초기화--------
    	index = Integer.parseInt(br.readLine());
    	num = new int[index];
    	for(int i=0;i<index;i++) 
        	num[i] = Integer.parseInt(br.readLine());
    
    	Arrays.sort(num);	//배열 오름차순 정렬
		int temp = num[1] - num[0];
    	for(int i=2;i<index;i++) 	//최대 공약수 구하기
    		temp = GCD(temp, num[i]-num[i-1]);
    	
    	for(int i=2;i<=temp;i++) 	//최대 공약수의 약수 구하기
    		if(temp%i==0)
    			sb.append(i + " ");
    	
    	bw.write(sb.toString() + "\n");		//결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
    //----------최대 공약수 구하는 함수--------
    //유클리드 호제법
	public static int GCD(int num1, int num2) {
		if(num2==0)
			return num1;
		else
			return GCD(num2, num1%num2);
	}
}