백준 - 9613번 - GCD 합

9613번

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int num = Integer.parseInt(bf.readLine());
		for (int i = 0; i<num; i++) {
			st = new StringTokenizer(bf.readLine());
			int A = Integer.parseInt(st.nextToken());

			int[] arr = new int[A];
			for (int j = 0; j<A; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}

			long sum = 0;
			for (int j = 0; j<arr.length-1; j++) {
				for (int k = j+1; k<arr.length; k++) {
					sum += solve(arr[j], arr[k]);
				}
			}
			sb.append(sum).append('\n');
		}
		System.out.print(sb);
	}

	static int solve(int A, int B) {
		int R = 0;
		while (B != 0) {
			R = A % B;
			A = B;
			B = R;
		}

		return A;
	}
}

풀이

---

숫자 들을 입력받고 모든 조합의 최대공약수의 합을 구하는 문제다.

모든 조합이 매칭될 수 있도록 2중 for문을 사용했다.

기존에 sum을 int형으로 해놔서 문제가 계속 틀렸는데 long으로 변경하고 통과했다.

입력받는 숫자의 범위가 백만이라 안심하고 int를 썼지만 백만이라는 숫자가 백개 있고 최악의 입력값이라면 int가 위험할 수도 있겠다는 생각에 long으로 바꿔본 시도가 좋았다.