https://www.acmicpc.net/problem/9613
1. 아이디어
GCD의 쌍은 유클리드 호제법을 활용하면 간단하게 구할 수 있다.
2. 문제풀이
중복이 가능하기 때문에 반복문에서 유클리드 호제법으로 최대 공약수를 반복해서 구하면 간단하게 해결할 수 있다.
이때 최대 공약수의 합은 int형 오버플로우가 발생할 수 있는 점에 주의해야 한다.
3. 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= T; tc++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// int형 오버플로우 발생 가능
long sum = 0;
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
sum += gcd(arr[i], arr[j]);
}
}
sb.append(sum).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
private static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}
4. 후기
'코딩테스트 준비 > 백준' 카테고리의 다른 글
[백준] 15965번 - K번째 소수 [Java] (1) | 2024.12.04 |
---|---|
[백준] 1735번 - 분수 합 [Java] (0) | 2024.12.04 |
[백준] 12779번 - 상품 is 뭔들 [Java] (0) | 2024.12.03 |
[백준] 9506번 - 약수들의 합 [Java] (0) | 2024.12.03 |
[백준] 1037번 - 약수 [Java] (0) | 2024.12.03 |