9613_GCD 합 (JAVA)

9613번: GCD 합

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

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

			int[] num = new int[tokencount-1];
			for(int j=0; j<tokencount-1; j++){
				num[j] = Integer.parseInt(st.nextToken());
			}

			int[] ssang = new int[2];
			List<Integer> ans = new ArrayList<>();

			func(num, ssang, 0, 0, ans);

			long sum = 0;
			Iterator<Integer> it = ans.iterator();
			while(it.hasNext()){
				sum += it.next();
			}
            
			System.out.println(sum);
		}
	}

	private static void func(int[] num, int[] ssang, int num_index, int ssang_index, List<Integer> ans){
		if(ssang_index == 2){
			ans.add(gcd(ssang[0], ssang[1]));
			return;
		}
		if(num_index >= num.length)
			return;

		ssang[ssang_index] = num[num_index];
		func(num, ssang, num_index+1, ssang_index+1, ans);
		func(num, ssang, num_index+1, ssang_index, ans);
	}

	private static int gcd(int x, int y) {
		while(x>0){
			int temp = y%x;
			y = x;
			x = temp;
		}
		return y;
	}
}

 

1. num[] 원소를 2개 택하는 모든 경우를 조합으로 구한다. : func()함수

2. 2개를 택했을 때, 최대공약수를 구하고 ans리스트에 넣는다.

3. 총 합 출력하면 끝

 

** 정답은 int형의 범위를 넘어갈 수 있다. long형으로 선언해야 한다.