[백준] 약수, 배수와 소수2_1

서론

---

약수, 배수와 소수 2 

1 ~ 3 문제풀이

---

1934 : 최소공배수

---

문제

---

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

1934번: 최소공배수

---

해설

---

처음에는 아래의 코드처럼 무작정

1부터 A * B까지의 수로 A와 B를 나누어서 둘 다 나누어 떨어지면, 공배수이므로, 이를 출력하고자 하였다.

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

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));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            for (int j = 1; j <= (A*B); j++) {
                if(j % A == 0 && j % B == 0){
                    sb.append(j).append("\n");
                    break;
                }
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

하지만 시간초과가 나왔다. (당연..ㅎ)

---

그래서 유클리드 호제법을 사용해보기로 하였다.

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

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));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int g = gcd(A,B);
            sb.append(A * B / g).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int gcd(int a, int b) {
        if(a % b == 0){
            return b;
        }
        return gcd(b, a%b);
    }
}

 

유클리드 호제법에 대해서는 다음에 자세히 다뤄보도록 하겠다.

---

13241 : 최소공배수

---

문제

---

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

13241번: 최소공배수

---

해설

---

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

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        long g = gcd(N, M);
        StringBuilder sb = new StringBuilder();
        sb.append(N * M / g);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static long gcd(long a, long b) {
        if(a % b == 0){
            return b;
        }
        return gcd(b, a%b);
    }
}

이 문제도 동일하게 유클리드 호제법을 사용하였다.

하지만, 처음에는 int형으로 사용했다가 틀렸다..

입력에 long을 쓰라고 이미 알려줬는데, 문제 좀 잘 읽자..ㅋㅋ

---

1735 : 분수 합

---

문제

---

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

1735번: 분수 합

---

해설

---

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

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long A1 = Long.parseLong(st.nextToken());
        long B1 = Long.parseLong(st.nextToken());
        st = new StringTokenizer(br.readLine());
        long A2 = Long.parseLong(st.nextToken());
        long B2 = Long.parseLong(st.nextToken());

        long B = B1 * B2;
        long A = (A1 * B2) + (A2 * B1);
        long g = gcd(A,B);

        StringBuilder sb = new StringBuilder();
        sb.append(A/g).append(" ").append(B/g);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static long gcd(long a, long b) {
        if(a % b == 0){
            return b;
        }
        return gcd(b, a%b);
    }
}

이 문제는 분수의 합을 기약분수로 출력하는 문제이다.

먼저, 통분을 해주기 위해, 각 분모를 곱해주고, 분자에 각각 분모를 곱해주었다.

이를 공식으로 표현하면 아래와 같다.

그리고 마지막으로 기약분수로 만들어주기 위해서 A,B의 최대공약수로 이를 나누어 주었다.

---

결론

---

유클리드 호제법을 잊고 있었는데, 자세히 알아보아야 겠다.

---