[알고리즘] 백준 - 2609번 : 최대공약수와 최소공배수 / 1934번 : 최소공배수 / 9613번 : GCD 합

알고리즘 문제 출처 : https://www.acmicpc.net/problem/2609

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

 

내가 작성한 코드

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

public class Main {
	public static int gcd(int a, int b) { //최대공약수
		if(b==0) {
			return a;
		}else {
			return gcd(b, a%b);
		}
	}
	
	public static int lcm(int a, int b) { //최소공배수
		int gcd = gcd(a, b);
		return gcd * (a/gcd) * (b/gcd);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] numList = br.readLine().split(" ");
		int a = Integer.parseInt(numList[0]);
		int b = Integer.parseInt(numList[1]);
		bw.write(gcd(a,b)+"\n"+lcm(a,b));
		bw.flush();
		bw.close();
	}
	
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

내가 작성한 코드

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

public class Main {
	
	public static int lcm(int a, int b) {
		int tempA = Math.max(a, b);
		int tempB = Math.min(a, b);
		while(tempB!=0) {//최대공약수 tempA 구하기
			int r = tempA % tempB;
			tempA = tempB;
			tempB = r;
		}
		return tempA * (a/tempA) * (b/tempA);//최소공배수 리턴
	}
	
	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 n = Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			String[] numList = br.readLine().split(" ");
			int a = Integer.parseInt(numList[0]);
			int b = Integer.parseInt(numList[1]);
			bw.write(lcm(a,b)+"\n");
		}
		bw.flush();
		bw.close();
	}
	
}

 

 

---

알고리즘 문제 출처 : https://www.acmicpc.net/problem/9613

9613번: GCD 합

 

내가 작성한 코드

합이 int형이면 부족해서 틀렸다고 뜬다. long형으로 해줘야 넉넉하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static int gcd(int a, int b) {
		if(b == 0) {
			return a;
		}else {
			return gcd(b, a%b);
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for(int i=0; i<n; i++) {
			String[] input = br.readLine().split(" ");
			int m = Integer.parseInt(input[0]);
			long sum = 0;
			for(int j=1; j<m; j++) {
				for(int l=j+1; l<=m; l++) {
					int a = Integer.parseInt(input[j]);
					int b = Integer.parseInt(input[l]);
					sum += gcd(a,b);
				}
			}
			System.out.println(sum);
		}
	}
}