Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Archives
Today
Total
관리 메뉴

전공공부

[BOJ_2436] 공약수 본문

Study/Problem Solving

[BOJ_2436] 공약수

monitor 2023. 12. 5. 08:24

설명


최대공약수 * 최소공배수를 진행하면 내가 뽑을 수도 같은 숫자를 가질 수 있다는 것은 파악을 하였다. 하지만, 이를 서로소로 만들어서 풀 생각은 하지 못하였는데 그냥 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번: 공약수

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0

www.acmicpc.net

 

'Study > Problem Solving' 카테고리의 다른 글

[BOJ_1188] 음식 평론가  (2) 2023.12.08
[BOJ_3343] 장미  (0) 2023.12.07
[BOJ_1990] 소수인 팰린드롬  (1) 2023.12.04
[BOJ_1669] 멍멍이 쓰다듬기  (1) 2023.12.03
[BOJ_1456] 거의 소수  (2) 2023.12.02