유클리드 호제법

• 두 수의 최대 공약수를 구하는 알고리즘

최소 공배수 구하기

Question - 1934

Code

import java.util.Scanner;

public class N21_P1934_최소공배수구하기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        for (int i = 0; i < N; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int result = a * b / gcd(a, b);
            System.out.println(result);
        }
    }

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

Insight

Idea

• 수학

• 정수론

• 유클리드 호제법

reference

최대 공약수 구하기

Question - 1850

Code

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class N43_P1850_최대공약수_구하기 {

    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(
            new OutputStreamWriter(System.out));

        long a = sc.nextLong();
        long b = sc.nextLong();
        long result = gcd(a, b);
        while (result > 0) {
            bw.write("1");
            result--;
        }

        bw.flush();
        bw.close();
    }

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

Insight

• 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다.

• 즉, 3,6의 최대 공약수 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타낸다.

Idea

• 수학

• 정수론

• 유클리드 호제법

reference

칵테일 만들기

Question - 1033

Code

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class N44_P1033_칵테일_만들기 {

    static ArrayList<cNode>[] A;
    static long lcm;
    static boolean visited[];
    static long D[];

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(
            new OutputStreamWriter(System.out));
        int N = sc.nextInt();
        A = new ArrayList[N];
        visited = new boolean[N];
        D = new long[N];
        lcm = 1;

        for (int i = 0; i < N; i++) {
            A[i] = new ArrayList<cNode>();
        }

        for (int i = 0; i < N - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p = sc.nextInt();
            int q = sc.nextInt();

            A[a].add(new cNode(b, p, q));
            A[b].add(new cNode(a, q, p));
            lcm *= (p * q / gcd(p, q));
        }

        D[0] = lcm;
        DFS(0);
        long mgcd = D[0];
        for (int i = 1; i < N; i++) {
            mgcd = gcd(mgcd, D[i]);
        }
        for (int i = 0; i < N; i++) {
            System.out.print(D[i] / mgcd + " ");
        }
    }

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

    public static void DFS(int Node) {
        visited[Node] = true;
        for (cNode i : A[Node]) {
            int next = i.getB();
            if (!visited[next]) {
                D[next] = D[Node] * i.getQ() / i.getP();
                DFS(next);
            }
        }
    }
}


class cNode {
    int b;
    int p;
    int q;

    public cNode(int b, int p, int q) {
        super();
        this.b = b;
        this.p = p;
        this.q = q;
    }

    public int getB() {
        return b;
    }

    public int getP() {
        return p;
    }

    public int getQ() {
        return q;
    }
}

Insight

Idea

• 수학

• 그래프 이론

• 그래프 탐색

• 정수론

• 유클리드 호제법

reference