[BOJ_2436] 공약수

설명

---

최대공약수 * 최소공배수를 진행하면 내가 뽑을 수도 같은 숫자를 가질 수 있다는 것은 파악을 하였다. 하지만, 이를 서로소로 만들어서 풀 생각은 하지 못하였는데 그냥 1~N까지 모두 탐색하면 시간초과가 날것이 뻔하니 최대공약수로 나눠서 탐색하면 x,y값 모두 서로소가 되고 이때 최대 공약수를 곱해서 GCD 여부가 같은지 체크하면 된다.

 

6 * 180 = 30 * 36 -> x,y 모두 서로소로 만들기 위해서 모든 변수에 GCD로 나눈다. => 1 * 30 = 5 * 6

 

이런 형태가 나올 것이고 이를 아래와 같은 코드로 구현하였다.  

 

코드

---

package Math;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_2436 {
    static class Data implements Comparable<Data>{
        int x;
        int y;
        public Data(int x,int y){
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Data o) {
            return Integer.compare((this.x + this.y),(o.x + o.y));
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        PriorityQueue <Data> pq = new PriorityQueue<>();
        int A = Integer.parseInt(tk.nextToken());
        int B = Integer.parseInt(tk.nextToken());

        int tmp = B/A;
        for (int i = 1; i <= tmp; i++){
            if(tmp % i == 0){
                int b = tmp / i;
                if(A == GCD(i*A,b*A)) {
                    pq.add(new Data(i, b));
                }
            }
        }
        int x = pq.peek().x * A;
        int y = pq.peek().y * A;
        System.out.println(x > y ? y + " " + x : x + " " + y);
    }
    private static int GCD(int a,int b){
        if(b == 0){
            return a;
        }
        return GCD(b, a%b);
    }
}

 

2436번: 공약수