[JAVA][BOJ][S3] 9613. GCD 합

9613번: GCD 합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

풀이

GCD, 즉 최대공약수를 구하는 문제다 나머지 연산과 빼기를 이용해서 풀었다

1번 풀이

유클리드 호제법(나머지 연산)

1. 큰 수를 작은 수로 나눈다

2. 작은 수를 큰 수로, 나머지를 작은 수로 계산해 다시 나눈다

3. 나머지가 0일 때 마지막으로 나누는 수(작은 수)가 최대공약수

 

2번 풀이

빼기 연산

1. 큰 수와 작은 수를 구분한다

2. 작은 수부터 1까지 for문을 이용해 나누다가 큰 수와 작은 수 모두 나머지가 0이 되면 그 수가 최대공약수

3. 1부터 작은 수까지 역순으로 나누게 되면 모든 수를 다 체크해야 하기 때문에 시간 초과가 날 수 있다

코드

package 문제풀이;

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

public class S3_9613_GCD합 {
	static int n;
	static long sum;
	static int[] input, numbers;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int t = Integer.parseInt(br.readLine());
		
		for (int tc = 0; tc < t; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			n = Integer.parseInt(st.nextToken());
			input = new int[n];
			numbers = new int[2];

			for (int i = 0; i < n; i++) {
				input[i] = Integer.parseInt(st.nextToken());
			}
			
			sum = 0;
			combi(0, 0);
			
			sb.append(sum + "\n");
			
		}
		
		System.out.println(sb);

	}

	private static void combi(int cnt, int start) {

// 		1번 풀이
		if(cnt==2) {
			int min = Math.min(numbers[0], numbers[1]);
			int max = 0;
			
			
			for (int i = min; i >= 1; i--) {
				if(numbers[0]%i==0 && numbers[1]%i==0) {
					max = i;
					break;
				}
			}
			
			sum += max;
			
			return;
		}

// 		2번 풀이
//		if(cnt==2) {
//			int n1 = numbers[0];
//			int n2 = numbers[1];
//			
//			while(true) {
//				int tmp = n1%n2;
//				if(tmp!=0) {
//					n1 = n2;
//					n2 = tmp;
//					continue;
//				} else {
//					sum += n2;
//					return;
//				}
//				
//			}
//		}
		
		for (int i = start; i < n; i++) {
			numbers[cnt] = input[i];
			combi(cnt+1, i+1);
		}
		
	}

}

 

결과

위부터 2번, 1번 풀이. 메모리와 시간 차이는 없다

 

#자바 #java #boj #백준 #알고리즘