[JAVA] 백준 9613번

9613번 - GCD 합

 

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

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));

		int t = Integer.parseInt(br.readLine());

		for (int i = 0; i < t; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			int n = Integer.parseInt(st.nextToken());

			int[] numbers = new int[n]; // 입력받은 수들

			long sum = 0;

			for (int j = 0; j < n; j++) {
				numbers[j] = Integer.parseInt(st.nextToken());
			}

			for (int k = 0; k < n; k++) {
				for (int l = k + 1; l < n; l++) {
					sum = sum + gcd(numbers[k], numbers[l]);
				}
			}

			bw.write(String.valueOf(sum));
			bw.newLine();
		}

		bw.flush();
		bw.close();
	}

	private static int gcd(int i, int j) {

		if (i % j == 0) {
			return j;
		} else {
			return gcd(j, i % j);
		}

	}

}

 

처음 문제에 접근한 방식

1. 입력받은 수들을 2중 for문과 유클리우드 호제법을 통해 gcd를 구함

2. 오답처리되어 중복된 순서쌍의 경우 한번만 값을 더해야하나 생각함

3. 문제원인은 sum의 자료형을 int형으로 선언했기 때문

 

정답을 맞춘 풀이방법

1 . sum 의 최대값은 20억이 넘어감으로 자료형을 long으로 바꿔줌