백준 2981 - 검문 JAVA(feat. koosaga님)

문제, 입출력, 테스트케이스

해당문제는 한 15분 고민하다가 과감하게 구글링을 한 문제이다.

결국 유클리드 호제법을 사용하는 문제인데 그 전에 유도식이 존재한다.

<문제 접근/풀이과정>

A와 B를 나눠서 나머지가 같다라는 말을 식으로 표현하자면

A = a*M + spare

B = b*M + spare

-> A - B = M * (a - b) 가 성립된다결국 M*(a-b)을 구하는 문제에 해당하므로 M*(a-b)의 약수들의 집합이 답이다.

A, B, C가 있다면

A와 B의 M*(a-b)값과 B-C의 값인 M*(b-c)의 최대공약수(gcd)를 계속 구하여 그 최대공약수의 약수의 집합을 오름차순으로 나열하면 되는 문제이다.

유클리드 호제법의 경우  위키피디아를 보면 잘 나와 있으므로 참고하시라!
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

문제를 풀고보니 내 소스코드의 시간이 1540ms나 되어서 앞서 푸신 분들 중 볼만한 코드를 찾다가 킹오브킹, 레전드오드레전드인 koosaga님의 C++ 코드가 있어서 읽고 바로 이해한 후 java로 따라 쳐봤다.(허락 없이 사용해서 죄송합니다 ㅜㅜ) 

koosaga님께 배운 테크닉은 오름차순 정렬을 할 필요 없이 특정 수의 약수를 오름차순 출력하는 테크닉으로 매우 고급진 테크닉이다... 이래서 백준 1등이신가보다!!!

 

 

1. 본인의 코드(1540ms)

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1. 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.
		// 2. 2 <= 적은 숫자의 갯수 N <= 100, 1 <= 종이에 적힌 각각의 수 <=1,000,000,000 -> int형 선언
		// 3. 같은 수가 두 번 이상 주어지지 않음 => 딱 한 번 주어짐
		// 제한시간 1초 -> 10억번 연산 불가 (시간 초과)
		// 6 34 38
		// 28 4
		// 2, 4
		// 5 14 17 23 83
		// 3
		// 9 3 6 60
		
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		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 = 1; i < N-1; i++) {
			gcdVal = gcd(gcdVal, arr[i+1] - arr[i]);
		}
		
		for (int i = 2; i <= gcdVal; i++) {
			if(gcdVal % i == 0)sb.append(i).append(" ");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static int gcd(int a, int b) {
		while(b!= 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}

 

2. koosaga님 코드 변형(76ms)

package boj;

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

public class Boj_2981 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1. 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.
		// 2. 2 <= 적은 숫자의 갯수 N <= 100, 1 <= 종이에 적힌 각각의 수 <=1,000,000,000 -> int형 선언
		// 3. 같은 수가 두 번 이상 주어지지 않음 => 딱 한 번 주어짐
		// 제한시간 1초 -> 10억번 연산 불가 (시간 초과)
		// 6 34 38
		// 28 4
		// 2, 4
		// 5 14 17 23 83
		// 3
		// 9 3 6 60
		
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		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 = 1; i < N-1; i++) {
			gcdVal = gcd(gcdVal, arr[i+1] - arr[i]);
		}
		
		int i;
		for (i = 2; i*i <= gcdVal; i++) {
			if(gcdVal % i == 0)sb.append(i).append(" "); 
		}
		
		while(i-->1) {
			if(i*i == gcdVal) continue;
			if(gcdVal % i == 0) sb.append(gcdVal / i).append(" ");
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb.toString());
	}

	private static int gcd(int a, int b) {
		while(b!= 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}