문제
- 최소공배수를 구하는 방법
1-1. 최소공배수... 가물가물한데 일단 소인수분해를 사용하는 것 정도만 기억이난다.
1-2. 근데 그러면 숫자 2개 모두 계속 나눠야 하는데... 반복문으로 하면 시간이 너무 많이 걸리거 같고... 숫자가 커지면 힘들거 같은데...
시도
- 일단 45000까지로 숫자 크기를 제한해두었으니 해보도록 하자
1-1. 두 숫자를 입력받고 재귀함수를 만들어서 소인수 분해를 해봄
-> 나오기는 함. 근데 시간초과.....
-> 뭔가 최소공배수를 구하는 공식이 있었던 걸로 기억하는데...
해결
- 혼자서 무슨 방법이 있지 않을까 삽질을 하다가 결국 시간이 너무 많이 소모되어서 검색을 해보았다.
1-1. 유클리드 호제법이라는 공식이 있는데 그것이 최소공배수를 구할 수 있다고 함
1-2. 해당 공식을 가지고 재귀 함수를 사용해서 최소 공배수를 구함
-> 해결
알게 된 점
- 최소 공배수와 최대 공약수
1-1. 유클리드 호제법 (최소 공배수)자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라 한다면 a,b의 최대공약수와 b,r의 최대공약수는 같다.
이 성질에 따라 a를 b로 나눈 나머지 r을 구하고, b를 r로 나눈 나머지 r'을 구한다.
나머지가 0이 될때 나눈 수가 a,b의 최대공약수가 된다.
최소 공배수 : (a ✕ b) / (최대 공약수)
예를 들면 30과 6이 있을 때 30을 6으로 나누면 나머지가 0이니까 30과 6의 최대공약수는 6이 된다.
이를 토대로 최소 공배수를 구하면 30 * 6 / 6 = 30 이라서 최소공배수는 30이 된다.
=> 이런 공식이 있었다니... 정말 천재들은 많구나...
오늘 푼 문제
주제 : 약수, 배수와 소수
백준 1934 (최소공배수) - Java
import java.io.*;
import java.util.*;
public class Main {
// 최소공배수를 구하는 함수 (유클리드 호제법)
public static int GCD (int big, int small) {
if (big % small == 0) return small;
return GCD(small, big % small);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int test_case = 0;
test_case = Integer.parseInt(st.nextToken());
for (int i = 0; i < test_case; i++) {
int max = 0, min = 0;
st = new StringTokenizer(br.readLine(), " ");
max = Integer.parseInt(st.nextToken());
min = Integer.parseInt(st.nextToken());
int temp = 0;
if (max < min) {
temp = max;
max = min;
min = temp;
}
int res = max * min / GCD(max, min);
bw.write(res + "\n");
}
bw.flush();
bw.close();
br.close();
}
}백준 13241 (최소공배수) - Java
위에서 푼 문제랑 차이가 없다. 다만 처음에 변수 선언할때 int 가 아니라 long으로 선언하자.
import java.io.*;
import java.util.*;
public class Main {
public static Long GCD (Long big, Long small) {
if (big % small == 0) return small;
return GCD(small, big % small);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
long max = 0, min = 0;
max = Long.parseLong(st.nextToken());
min = Long.parseLong(st.nextToken());
long temp = 0;
if (max < min) {
temp = max;
max = min;
min = temp;
}
Long res = max * min / GCD(max, min);
bw.write(String.valueOf(res) + "\n");
bw.flush();
bw.close();
br.close();
}
}백준 1735 (분수 합)
분수합을 구하는 방법 ex) a/b + c/d
- 분모 : b * d
- 분자 : a * d + b + c
- 여기에서 기약분수를 구하고 싶다면 결과로 나온 분모와 분자의 최대공약수로 각각을 나눠주면 될 듯
import java.io.*;
import java.util.*;
public class Main {
public static int GCD (int big, int small) {
if (big % small == 0) return small;
return GCD(small, big % small);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 그냥 2차원 배열 만듬
int[][] arr = new int[2][2];
for (int i = 0; i < 2; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int up = 0, down = 0;
up = Integer.parseInt(st.nextToken());
down = Integer.parseInt(st.nextToken());
// 분자, 분모를 각각 arr에 할당
arr[i][0] = up;
arr[i][1] = down;
}
// 분자 = 첫번째 분자 * 두번째 분모 + 두번째 분자 * 첫번째 분모
int up = arr[0][0] * arr[1][1] + arr[0][1] * arr[1][0];
// 분모 = 첫번째 분모 * 두번째 분모
int down = arr[0][1] * arr[1][1];
// 최대공약수
int gcd = GCD(down, up);
// 기약분수가 되기 위해서 최대 공약수로 분자와 분모를 각각 나눠줌
up = up / gcd;
down = down / gcd;
bw.write(String.valueOf(up) + " " + String.valueOf(down));
bw.flush();
bw.close();
br.close();
}
}백준 2485 (가로수) - Java
이 문제 또한 최대공약수를 구하면 해결되는 문제긴 하다.
다만 여기서의 최대공약수는 입력받은 숫자들의 최대 공약수가 아니라 각 숫자간의 차이 (거리) 들의 최대 공약수이다.
예를 들어 1 3 5 9 가 입력되었다면 3-1, 5-3, 9-5의 최대 공약수를 구하는 것
또한 앞선 문제들은 두 숫자의 최대공약수를 구하면 되지만 이 문제는 숫자가 많이 입력되기 때문에 처음 두 수의 최대 공약수를 구하고, loop를 통해서 뒤의 숫자들과의 최대 공약수를 구하면 될 듯
import java.io.*;
import java.util.*;
public class Main {
public static int GCD (int big, int small) {
if (big % small == 0) return small;
return GCD(small, big % small);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int tCase = Integer.parseInt(st.nextToken());
// 입력받은 값을 더할 ArrayList와 그 ArrayList의 인덱스들을 뺄 ArrayList를 생성
ArrayList<Integer> arr = new ArrayList<>();
ArrayList<Integer> arr2 = new ArrayList<>();
// 첫번째 ArrayList에 숫자들을 입력받고
// 두번째 ArrayList에 숫자들의 차를 할당한다.
for (int i = 0; i < tCase; i++) {
st = new StringTokenizer(br.readLine());
arr.add(Integer.parseInt(st.nextToken()));
if (i != 0) arr2.add(arr.get(i) - arr.get(i - 1));
}
// 처음 두 수의 최대 공약수
int gcd = GCD(arr2.get(0), arr2.get(1));
// 만약에 숫자가 3개만 입력되었다면 처음 구한 최대 공약수가 최종적인 최대 공약수
if (arr2.size() != 3)
for (int i = 2; i < arr2.size(); i++) {
gcd = GCD(gcd, arr2.get(i));
}
// count되는 값은 해당 차이들을 최대 공약수로 나눈 값들을 전부 더한 후
// 입력 받은 갯수 - 1 (=> 차이들의 갯수) 만큼 빼주면 된다.
int count = 0;
for (int i = 0; i < tCase - 1; i++)
count += arr2.get(i) / gcd;
bw.write(String.valueOf(count - tCase + 1));
bw.flush();
bw.close();
br.close();
}
}백준 4134 (다음 소수) - Java
이 부분에서 헷갈렸던 것은 숫자를 하나씩 증가시켜가면서 그 증가된 숫자가 소수인지 계속 확인하는 것이였는데, 메서드 2개 만들어서 하나는 증가시키는거, 하나는 소수인지 확인하는 걸로 해결
참고로 0이랑 1일 때도 들어가니까 주의
for문을 2개사용하는 셈이라 시간초과가 나올 것으로 예상했는데 안나왔다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long test = Long.parseLong(br.readLine());
for (int i = 0; i < test; i++) {
long num = Long.parseLong(br.readLine());
// primeNum(num) 메서드 호출 => num은 입력 값
bw.write(String.valueOf(primeNum(num)) + "\n");
}
bw.flush();
bw.close();
br.close();
}
// 해당 입력값부터해서 하나씩 증가시켜가면서 소수인지 확인하고 맞으면 return
// 입력 값이 0이나 1이면 2를 return
public static long primeNum(long num){
long res = 0;
if (num == 0 || num == 1) return 2;
for(long i = num; ; i++){
if (isPrime(i)) {
res = i;
return res;
}
}
}
// 받은 값이 소수인지 확인하는 메서드
public static boolean isPrime(long num) {
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) return false;
}
return true;
}
}