- 생각
처음 풀어보니 시간초과가 떴다. 다른 사람이 잘 정리해놓은 것을 가져왔다. (링크)
문제에서 매우매우 중요한 키워드가 두 개 있다.
첫 번째로 '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)의 공약수를 찾으면 된다는 것이다.
그러면 이제 공약수를 찾을 일만 남았다. 공약수를 찾는 방법은 매우 쉽지 않은가?
최대공약수가 무엇인가? 최대공약수는 '공약수들 중에서 가장 큰 값' 아니던가. 즉, 거꾸로 최대공약수를 찾고 최대공약수와 그의 약수들을 구하면 끝이다.
- 코드
정답 코드 : 유클리드 호제법을 이용하여 구현했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N, M;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(sb);
}
private static void SetData() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
sb = new StringBuilder();
int[] array = new int[N];
for(int i = 0; i < N ; i++)
array[i] = Integer.parseInt(br.readLine());
Arrays.sort(array);
int gcdValue = array[1] - array[0]; // 음수가 되지 않도록 큰 수에서 작은 수로 빼줌
for(int i = 2; i < N; i++) {
// 직전의 최대 공약수와 다음 수(array[i] - array[i - 1])의 최대공약수를 갱신
gcdValue = getGCD(gcdValue, array[i] - array[i - 1]);
}
for(int i = 2; i <= gcdValue; i++) {
// i가 최대공약수의 약수라면 출력
if(gcdValue% i == 0) {
sb.append(i + " ");
}
}
}
private static int getGCD(int p, int q) {
if (q == 0) {
return p;
}
return getGCD(q, p % q);
}
}'algorithm' 카테고리의 다른 글
| [JAVA] 백준 2302번 : 극장 좌석 (0) | 2020.12.22 |
|---|---|
| [JAVA] 백준 2294번 : 동전 2 (0) | 2020.12.21 |
| [JAVA] 백준 1739번 : 타일링 (0) | 2020.12.18 |
| [JAVA] 백준 11058번 : 크리보드 (0) | 2020.12.18 |
| [JAVA] 백준 11047번 : 동전 0 (0) | 2020.12.17 |
