[백준] 2981번 : 검문

글 작성자: ST_

www.acmicpc.net/problem/2981

2981번: 검문

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

www.acmicpc.net

문제

생각보다 정답비율이 엄청 낮은 문제다.. 필자도 작성과정에 실수한 것이 있어서 한 번 틀렸다만, 진짜 쉽게 풀 수 있는 문제다.

알고리즘 [접근 방법]

이 문제를 풀이하기 전에 먼저 최대공약수를 어떻게 풀이하는지, '유클리드 호제법'이 무엇인지를 알아야 할 필요가 있다. 한 번 아래의 포스팅 글을 보고 오면 좋을 것 같다.

최대공약수 알고리즘

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 알

st-lab.tistory.com

이 문제 체점 결과를 보니 시간 초과로 실패한 사람이 매우 많았다.

아마 가장 단순한 방법으로는 각 입력되는 수 끼리의 약수들을 구하고 각 수들의 약수 중 공통 된 것들을 뽑아내는 방법일 것이다.

예로들어 4 24 6 8 이 있으면 4와 24의 약수를 쭉 구하고, 24와 6의 약수들을 쭉 구하고 6과 8의 약수들을 쭉 구한 다음 공통 된 약수들만 뽑아내는 것이다.

근데 이렇게 하면 '시간초과'가 뜰 것이다.

다른 블로그들을 보니 설명을 다음과 같이 한다. (M : 나눈 수 r : 나머지(remainder))

임의의 정수 A₁과 A₂는 다음과 같이 표현 할 수 있다.

A₁ = M * a₁ + r₁

A₂ = M * a₂ + r₂

이 때 나머지가 같아야 하기 때문에 r₁과 r₂가 같아야 한다는 가정하에 A1에서 A2를 빼면 다음과 같이 만들 수 있다.

A₁ - A₂ = M * (a₁ - a₂) + (r₁ - r₂)

r₁ - r₂ = 0 이므로, A₁ - A₂ = M * (a₁ - a₂)

M 은 (A₁ - A₂) 의 약수이므로, A₁ 과 A₂ 의 공약수가 됨.

즉, 우리는 여기서 M을 찾아야 한다. 라는 말인데.. 이해가 잘 가시는가? (간다면 할 말은 없다만..)

이렇게 보아도 이해하면 정말 좋겠지만, 사실 기호로만 표현하자니 어렵게 다가오시는 분들도 많을 것이다. 그래서 좀 더 쉽게 이해할 수 있도록 설명을 해보고자 한다.

위의 문제 예제를 예로 들어보자. 우리는 문제에서 매우매우 중요한 키워드가 두 개 있다.

첫 번째로 'M이 하나 이상 존재하는 경우로만 주어진다' 이다.

두 번째로 '나머지가 모두 같게 되는 M을 찾으려고 한다' 이다.

이 두 문장을 잘 생각해보면 다음과 같다. '나머지가 같은 경우는 반드시 존재하며 이 때의 M은 모든 수에서 동일하다.'

그러면 모든 수에서 '동일하다'라는 의미는 결과적으로 M은 공약수라는 말 아니겠는가?

즉, 위 문제의 예제로 보면 이렇다는 것이다.

6 / M + r

34 / M + r

38 / M + r

여기서 r은 모두 같다는점. 즉, r만 0으로 만들 수 있다면 M을 쉽게 구할 수 있다는 것이다.

(6 / M + r) - (34 / M + r) 을 풀어서 다시 묶어 표현하면

(6 - 34) / M 이라는 식이 나온다.

다음으로 (34 / M + r) - (38 / M + r) 을 풀어서 다시 묶어 표현하면

(34 - 38) / 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)의 공약수를 찾으면 된다는 것이다.

그러면 이제 공약수를 찾을 일만 남았다. 공약수를 찾는 방법은 매우 쉽지 않은가?

최대공약수가 무엇인가? 최대공약수는 '공약수들 중에서 가장 큰 값' 아니던가. 즉, 거꾸로 최대공약수를 찾고 최대공약수와 그의 약수들을 구하면 끝이다.

그럼 본격적으로 알고리즘으로 구현해보도록 하자.

알고리즘 구현에 앞서 주의해야 할 것은 위 식에서 무작정 뺄셈을 해주면 '음수'가 나올 수도 있다. 그러니 수들을 입력을 받고 '정렬'을 해주어도 되고, 뺄셈을 한 값에 절댓값을 써도 된다. 어느 방법을 써도 무방하다.

필자는 조금 편하게 정렬을 이용해서 풀이하겠다. 아래는 간락햐게 표현한 코드다.

main() {
	int[] arr = new int[N];	// 입력받아 초기화 되어있는 상태라고 가정

	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++) {
    
		// i가 최대공약수의 약수라면 출력
		if(gcdVal% i == 0) {
			print(i);
		}
	}

}

// 최대공약수 함수
int gcd(int a, int b) {
	while(b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

여기서 참고할 점은 A, B, C, D, E 라는 수가 있을 때, (A-B), (B-C)의 최대공약수 gcdVal을 구하고, 그 다음에 (B-C), (C-D)의 최대공약수를 구하면 안된다.

모든 공약수가 같아야 한다는 점이기 때문에 (A-B), (B-C)에서 구해진 최대공약수 gcdVal은 (A-B), (B-C)의 공약수들 중 가장 큰 수인 것이고, 그 최대공약수 gcdVal과 (C-D)의 최대공약수를 구해야 (A-B), (B-C), (C-D) 의 최대공약수가 되는 것이다. 이 점 유의하도록 하자.

4가지 방법을 사용하여 풀이한다.

이번 문제는 특히 알고리즘 뿐만 아니라 출력 방법에도 큰 영향을 미친다. 수의 범위가 워낙 크다보니, 최대공약수가 매우 큰 수일 경우 그 최대공약수의 공약수들을 하나하나 출력하는 것도 큰 오버헤드이기 때문이다.

그래서 알고리즘은 위의 방법을 바탕으로 하나, Scanner 입력은 위 알고리즘대로만 하고, 나머지 3개의 케이스는 최대공약수의 약수를 찾는 방법을 달리하여 출력을 바꿔 어떻게 차이가 나는지 보여주도록 하겠다.

1 . Scanner + 기본 + System.out.println()

2. BufferedReader + 기본 + System.out.println()

3. BufferedReader + 범위 축소 + StringBuilder()

4. BufferedReader + Collection + StringBuilder()

풀이

- 방법 1 : [Scanner + 기본 + System.out.println()]

import java.util.Scanner;
import java.util.Arrays;

public class Main {	
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);

		int N = in.nextInt();
		
		int[] arr = new int[N];	
        
		for(int i = 0; i < N; i++) {
			arr[i] = in.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++) {
	    
			// i가 최대공약수의 약수라면 출력
			if(gcdVal % i == 0) {
				System.out.print(i + " ");
			}
		}
		
	}
	
	// 최대공약수 함수
	static int gcd(int a, int b) {
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

}

가장 기본적인 방법이라 할 수 있겠다.

그리고 항상 출력 형식 주의할 것

- 방법 2 : [BufferedReader + 기본 + System.out.println()]

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 알고리즘은 방법 1과 같다.

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


public class Main {	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		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++) {
	    
			// i가 최대공약수의 약수라면 출력
			if(gcdVal % i == 0) {
				System.out.print(i + " ");
			}
		}
		
	}
	
	// 최대공약수 함수
	static int gcd(int a, int b) {
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

}

이 방법도 생각보다 시간이 많이 걸릴 것이다.

- 방법 3 : [BufferedReader + 범위 축소 + StringBuilder]

최대공약수의 약수를 굳이 끝까지 탐색할 필요가 없다. 최대공약수 자신을 제외한 약수로 갖을 수 있는 수 중 최댓값이 최대공약수/2 값을 넘을 수 있는가? 없다. 즉, 굳이 약수를 찾는데 gcdVal까지 찾을 필요 없이 gcdVal의 절반까지만 탐색해도 된다.

물론 이 때 주의해야 할 것은 마지막에 최대공약수 자신도 출력해주어야 한다.

그리고 출력은 StringBuilder로 해주겠다.

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

public class Main {		
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		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]);
		}

		StringBuilder sb = new StringBuilder();
		
		// 최대공약수의 약수들 찾기 (절반까지만 탐색)
		for(int i = 2; i <= gcdVal / 2; i++) {
	    
			// i의 제곱 값이 최대공약수의 약수라면?
			if(gcdVal % i == 0) {
				sb.append(i + " ");
			}
		}
		
		// 마지막 최대공약수 꼭 출력해야함
		sb.append(gcdVal);
        
		System.out.println(sb);
		
	}
	
	// 최대공약수 함수
	static int gcd(int a, int b) {
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

}

여기 까지는 쉽게 쓸 수 있을 것이다.

- 방법 4 : [BufferedReader + Collection + StringBuilder]

저 위의 최대공약수의 공약수를 찾는 과정에서 좀 더 좋은 방법은 없을까?

예로들어 최대공약수가 16이라면, 16 % 2 == 0 일 때 2도 넣고, 8도 약수이니 넣고 싶은데..

확실히 범위가 줄어드니 좋을 것 같아 접근해본 방식이다. 즉, Collection에 있는 list를 써서 양쪽 원소를 동시에 넣어주고 마지막에 정렬만 해주고 출력하면 훨씬 좋을 것 같지 않은가?

그러면 탐색 범위도 (gcdVal / 2) 가 아닌 제곱근, 즉 √gcdVal 까지만 탐색해도 된다는 점이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;


public class Main {	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		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]);
		}

		StringBuilder sb = new StringBuilder();
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		// 최대공약수의 약수들 찾기 (제곱근까지만 탐색)
		for(int i = 2; i <= Math.sqrt(gcdVal); i++) {
	    
			// 제곱근이 gcdVal의 약수라면 중복추가를 방지하기 위해 한 번만 추가
			if(i * i == gcdVal) {
				list.add(i);
			}
			// i가 최대공약수의 약수라면 i와 나눈 몫 추가 
			else if(gcdVal % i == 0) {
				list.add(i);
				list.add(gcdVal / i);
			}
		}

		// 정렬 
		Collections.sort(list);
		
		for(int val : list) {
			sb.append(val).append(' ');
		}
		// 마지막 최대공약수 꼭 출력해야함
		sb.append(gcdVal);
		System.out.println(sb);
		
	}
	
	// 최대공약수 함수
	static int gcd(int a, int b) {
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}

}

참고로 제곱근까지만 탐색하니 주의해야 할 것은 i가 제곱근 값에 해당 될 때 중복해서 추가하지 않도록 처리를 해주어야 한다. 이 점 꼭 유의하도록 하자.

성능

채점 번호 : 23409313 - 방법 4 : BufferedReader + Collection + StringBuilder()

채점 번호 : 23409306 - 방법 3 : BufferedReader + 범위 축소 + StringBuilder()

채점 번호 : 23409304 - 방법 2 : BufferedReader + 기본 + System.out.println()

채점 번호 : 23409301 - 방법 1 : Scanner + 기본 + System.out.println()

결과에서 볼 수 있듯이 주어지는 정수가 워낙 큰지라 최대공약수의 약수를 찾는 과정에서도 큰 차이를 보인다.

정리

이 번 문제를 보면 아마 대부분의 사람들이 처음에 대부분 공약수에 대한 이해 또는 알고리즘의 시간복잡도 예상을 하지 못해서 틀렸거나 시간초과였을 것이다.

약간의 꿀팁이라면 꿀팁인데, 문제가 쉬운데 정답률이 낮다싶으면 주어지는 입력 또는 시간, 메모리를 확인해보고 코딩을 해보면 앵간 거의 통과한다.

필자가 수식을 쓰는 것을 그다지 좋아하지 않아서 좀 더 풀어서 알고리즘을 설명했는데, 만약 이해가 되지 않은 부분이 있다면 댓글 남겨주셨으면 한다. 물론 그 외의 다른 댓글도 언제나 환영이다. 만약 남겨주시면 최대한 빠르게 답변드리겠다.

저작자표시 비영리 변경금지

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

[백준] 11050번 : 이항 계수 1 - JAVA [자바] (17)	2020.10.27
[백준] 3036번 : 링 - JAVA [자바] (0)	2020.10.23
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바] (14)	2020.10.20
[백준] 1037번 : 약수 - JAVA [자바] (6)	2020.10.15
[백준] 5086번 : 배수와 약수 - JAVA [자바] (0)	2020.10.14

[백준] 2981번 : 검문 - JAVA [자바]

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

댓글

이 글 공유하기

티스토리툴바

'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글

댓글

이 글 공유하기

다른 글

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

[백준] 3036번 : 링 - JAVA [자바]

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

[백준] 1037번 : 약수 - JAVA [자바]

티스토리툴바