BEAKJOON / 백준 - JAVA 9613번 GCD 합

2024.08.13기준 - 실버4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 수열에서 모든 쌍의 최대공약수를 더 해 값을 출력하는 문제입니다.

 

주의할 점은 전체 합은 int범위를 넘어가기 때문에, long을 사용해야 된다는 점입니다.

 

예제를 통해서 문제의 설명을 하도록 하겠습니다.

수열 : 10 20 30 40

 

1. 저는 List<boolean[]>을 통해 각 수의 약수들을 전부 true를 통해 저장을 해주었습니다.

static List<boolean[]> list;

public static void main(String[] args) throws IOException {
	list = new LinkedList<>();
    
    st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken()); // 숫자의 개수

    for (int i = 0; i < n; i++) {
        num = Integer.parseInt(st.nextToken());
        divisor(num, i);
    }
}

// 약수를 찾아주는 함수.
private static void divisor(int num, int index) {
    list.add(new boolean[num + 1]);

    for (int i = 1; i <= num; i++) {
        if (num % i == 0) {
            list.get(index)[i] = true;
        }
    }
}

 

수열 10, 20, 30, 40의 약수들을 구하면 이렇게 나오게 됩니다.

 

2. 여기 서 서로 같은 값을 가지면서 가장 큰 값을 출력해 줍니다.

for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        sum += maxnum(i, j);
    }
}

 

함수

// 2개의 리스트에서 최대공약수를 찾아주는 함수.
private static int maxnum(int a, int b) {
    for (int i = (list.get(a).length > list.get(b).length ? list.get(b).length - 1 : list.get(a).length - 1); i >= 0; i--) {
        if (list.get(a)[i] && list.get(b)[i]) {
            return i;
        }
    }

    return 1;
}

 

10과 20 (현재 합 : 10)

 

10과 30 (현재 합 : 20)

 

10과 40 (현재 합 : 30)

 

20과 30 (현재 합 : 40)

 

20과 40 (현재 합 : 60)

 

30과 40 (현재 합 : 70)

 

3. 이렇게 다 더해진 합을 출력합니다.

 

 

코드

package Main;

import java.io.*;
import java.util.*;

public class Main {
	
	static List<boolean[]> list;
	
	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();
		int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수
		
		int n, num;
		long sum;
		StringTokenizer st;
		while (t-- > 0) {
			list = new LinkedList<>();
			sum = 0;
			
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken()); // 숫자의 개수
			
			for (int i = 0; i < n; i++) {
				num = Integer.parseInt(st.nextToken());
				divisor(num, i);
			}
			
			for (int i = 0; i < n - 1; i++) {
				for (int j = i + 1; j < n; j++) {
					sum += maxnum(i, j);
				}
			}
			
			sb.append(sum).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 2개의 리스트에서 최대공약수를 찾아주는 함수.
	private static int maxnum(int a, int b) {
		for (int i = (list.get(a).length > list.get(b).length ? list.get(b).length - 1 : list.get(a).length - 1); i >= 0; i--) {
			if (list.get(a)[i] && list.get(b)[i]) {
				return i;
			}
		}
		
		return 1;
	}
	
	// 약수를 찾아주는 함수.
	private static void divisor(int num, int index) {
		list.add(new boolean[num + 1]);
		
		for (int i = 1; i <= num; i++) {
			if (num % i == 0) {
				list.get(index)[i] = true;
			}
		}
	}
}