백준 | 2609번, 9613번, 13241번, 1735번 - 유클리드 호제법 풀이

⬛ 백준 2609번. 최대공약수와 최소공배수 - 유클리드 호제법

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

💚나의 풀이

1) gcd(a,b) 함수로 최대공약수 구한다

2) 최소 공배수 = a *b /최대공약수

package to_1227_1;

import java.util.Scanner;

/**
 * 백준 최대공약수와 최소공배수 - gcd 유클리드 호제법 문풀 
 * 
 *
 */
public class Main {
	static int gcd(int a, int b) {
		int r = a % b;
		if(r == 0) return b;
		else return gcd(b, r);
	}
	
	//실행메인
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int a = kb.nextInt();
		int b = kb.nextInt();
		
		int g = gcd(a, b);
		int d = (a * b) / g;
		
		System.out.println(g);
		System.out.println(d);
		
	}
}

---

⬛ 백준 9613번. GCD 합 - 유클리드 호제법

https://www.acmicpc.net/problem/9613

9613번: GCD 합

💚나의 풀이

• 각 TC별로 이중 for문을 돌면서 각 두가지 숫자 쌍의 최대공약수를 구해서 list에 담고 그 합을 출력하면 된다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 9613번. gcd 합 
 * @author MYLG
 *
 */
public class Main {
	static int gcd(int a, int b) {
		int r = a % b;
		if(r == 0) return b;
		else return gcd(b, r);
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int TC = kb.nextInt();
		
		for(int t = 0; t<TC; t++) {
			int n = kb.nextInt();
			int[] arr = new int[n];
			List<Integer> list = new ArrayList<>();
			for(int i=0; i<n; i++) {
				arr[i] = kb.nextInt();
			}
			
			for(int i=0; i<n-1; i++) {
				int a = arr[i];
				for(int j = i+1; j<n; j++) {
					int b = arr[j];
					int g = gcd(a, b);
					list.add(g);
				}
			}			
			long sum = 0;
			for(int x : list) sum += x;
			
			System.out.println(sum);
		}
	}
}

---

⬛ 백준 13241번. 최소공배수 - 유클리드 호제법

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

💚나의 풀이

• 주의 : long 타입으로 구하기

package to_1227_3;

import java.util.Scanner;

/**
 * 13241번. 최소공배수 - gcd 활용
 * @author MYLG
 *
 */
public class Main {
	static long gcd(long a, long b) {
		long r = a % b;
		if(r==0) return b;
		else return gcd(b, r);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		
		long a = kb.nextLong();
		long b = kb.nextLong();
		
		long gcd = (a*b) /gcd(a, b);
		
		System.out.println(gcd);
	}
}

---

⬛ 백준 1735번. 분수 합 - 유클리드 호제법

https://www.acmicpc.net/problem/1735

1735번: 분수 합

💚나의 풀이

- 1) 공통분모 기준으로 분자도 통일시켜준다.

- 2) 만들어진 분수의 형태를 '기약분수' 형태로 만들어야 하므로 (분자, 분모)에 대한 최대공약수를 구한다.

- 3) 분자, 분모 각각에 '최대 공약수'로 나눈 값이 최종 '기약분수' 형태 답이 된다.

import java.util.Scanner;

/**
 * 1735번. 분수 합 - gcd 활용 
 */
public class Main {
	static int gcd(int a, int b) {
		int r = a % b;
		if(r==0) return b;
		else return gcd(b, r);
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int a = kb.nextInt();//분자
		int A = kb.nextInt();//분모
		
		int b = kb.nextInt(); //분자
		int B = kb.nextInt(); //분모 
		
		int M = A * B; //공통 분모 
		int m = (a*B) + (b * A); //분자 
		
		int gcd = gcd(M, m); //분수의 분자 분모를 기약분수로 만들 '최대공약수'
		// M, m에 각각 최대공약수로 나누고 나면 기약분수 형태가 된다.
		M /= gcd;
		m /= gcd;
		
		System.out.println(m + " " + M);
	}
}