문제
백준 2981 검문
문제 링크
https://www.acmicpc.net/problem/2981
문제 해석
숫자 N(2<=N<=100)개를 M으로 나눌 때 나머지가 모두 같게 되는 M 값을 모두 찾아야 하는 문제. 제일 관건은 M의 값의 조건이다. 1<=수<=10^9
만약 완전탐색으로 '모든 수를 M으로 나누었을 때 나머지가 같은 M을 찾는 경우의 수'를 따진다면, O(10^9 * 100)으로 시간 제한인 1초를 초과하게 된다.
이 문제는 완전탐색, 백트래킹 등 모든 경우의 수를 다 구하는 방법으로 푸는 것이 아니라는 걸 문제를 보고 바로 알 수 있었다.
문제 아이디어
주된 아이디어는 모듈러 연산, 유클리드 호제법이다.
간단하게 숫자가 3개 있다고 가정하면,
a, b, c 이렇게 3개의 숫자의 각각 mod k 연산의 값이 모두 같아야 한다.
a mod k = b mod k = c mod k
식으로 간단하게 나타낼 수 있다.
a mod k = b mod k
(a-b) mod k = 0 이라는 식을 도출할 수 있다. (모듈러 정리를 통해)
그럼 a와 b를 비교하는 식, b와 c를 비교하는 식, c와 a를 비교하는 식 모두 나타낼 수 있다. 여기서 a-b, b-a는 모두 Math.abs(a-b)를 나타낸다. 간단하게 나타내기 위함🥺
(a-b) mod k = (a-c) mod k = (b-c) mod k = 0 이라는 공식으로 정리할 수 있다.
그러면 여기서 a-b, a-c, b-c 는 k의 배수이다. (mod k 가 0이기 때문에 k로 나뉘어 진다 -> 배수임)
그럼 결론적으로 a-b, a-c, b-c의 공약수를 구하면 된다.
근데 두 수의 차 경우의 수에 대해 공약수를 모두 구하면 시간이 오래 걸릴 것이다.(그리고 번거로움) 그래서 효과적으로 최대공약수를 구해서 최대공약수의 약수를 구하는 방식으로 계산하도록 한다.
gcd(a-b, a-c) = g1
gcd(g1, b-c) = g2
결과적으로 g2가 세 수의 최대 공약수가 되고, 이 최대공약수의 약수를 구하면 이것이 정답이다. (최대 공약수의 약수들에 수를 곱하면 최대 공약수가 되기 때문에 결과적으로 해당 약수들로도 값이 나누어진다. diff mod 약수 = 0이라는 뜻)
주된 아이디어를 한 줄로 설명하자면, 나머지가 같은 수들은 나머지만큼 값이 차이가 난다는 뜻이고 -> 두 수의 차이를 구하면 이 값들은 무조건 k의 배수이다.
문제를 보면 완전탐색으로 시간초과가 난다는 걸 통해 완전탐색이 아니라는 걸 알 수 있고 나머지가 모두 같게 되는 M값 이라는 키워드에서 유클리드 호제법, 모듈러 연산을 떠올려야 한다.
코드
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args ) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] nums = new int[n];
for(int i=0;i<n;i++){
nums[i] = Integer.parseInt(br.readLine());
}
List<Integer> diff = new ArrayList<>();
findAllDiff(0, nums, 0, new int[2], diff);
int gcd = 0;
for(int i=0; i<diff.size(); i++){
gcd = getGcd(gcd, diff.get(i));
}
Integer[] res = getFactors(gcd);
Arrays.sort(res);
StringJoiner sj = new StringJoiner(" ");
for(int i=1;i<res.length;i++){
sj.add(Integer.toString(res[i]));
}
System.out.print(sj);
}
static Integer[] getFactors(int n){
Set<Integer> res = new HashSet<>();
for(int i = 1; i*i<=n; i++){
if(n % i == 0){
res.add(i);
res.add(n/i);
}
}
Integer[] resToArray = new Integer[res.size()];
return res.toArray(resToArray);
}
static int getGcd(int a, int b){
int n1 = Math.max(a, b);
int n2 = Math.min(a, b);
if(n2==0){
return n1;
}
return getGcd(n2, n1 % n2);
}
static void findAllDiff(int idx, int[] nums, int cnt, int[] res, List<Integer> diffs){
if(cnt == 2){
diffs.add(Math.abs(res[0]-res[1]));
return;
}
if(idx == nums.length){
return;
}
findAllDiff(idx+1, nums, cnt, res, diffs);
res[cnt] = nums[idx];
findAllDiff(idx+1, nums, cnt+1, res, diffs);
}
}
이 문제 골4인 게 안 믿긴다 진짜 어려웠음 ㅠ 방금 푼 골3은 20분 만에 풀었는데 이건 진짜 며칠만에 풀었다... 아무래도 수학적 이해가 부족한 탓인 것 같다. 그래도 덕분에 정수론도 다시 보고 유클리드 호제법도 공부하게 되어서 다행이라고 생각한다~!
3일 뒤에 다시 풀기
정수론 관련 다른 문제 더 풀기
https://www.acmicpc.net/problem/1644
https://www.acmicpc.net/problem/1963
https://www.acmicpc.net/problem/2436
https://www.acmicpc.net/problem/1188
https://www.acmicpc.net/problem/16563
https://www.acmicpc.net/problem/1990
