코딩테스트/자바 문제풀이

[수학] 백준 21920 서로소 평균

승요나라 2024. 8. 12. 23:18

21920번: 서로소 평균

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

 

# 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 수열 A를 담는 배열 arrA
        int[] arrA = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arrA[i] = Integer.parseInt(st.nextToken());
        }

        int x = Integer.parseInt(br.readLine());

        double sum = 0;
        double count = 0;
        for (int j = 0; j < n; j++) {
            // 유클리드 호제법
            // 몫, 나머지
            int quotient = Math.min(x, arrA[j]);
            int remainder = Math.max(x, arrA[j]) % quotient;

            // 나머지가 0이 될때까지 반복
            while (remainder != 0) {
                int num = quotient;
                quotient = remainder;
                remainder = num % quotient;
            }

            // 유클리드 호제법 : 나머지가 0이 될 때의 몫이 바로 두 수의 최대공약수임
            // 따라서 두 수의 최대공약수가 1이면 두 수는 서로소이다.
            if (quotient == 1) {
                sum += arrA[j];
                count++;
            }
        }

        System.out.println(sum/count);
        br.close();
    }
}
  • 우리가 익히 아는 최대공약수 로직 그대로 코드를 짜면 시간초과가 난다.
  • 따라서 유클리드 호제법을 이용했다.
  • 두 수의 최대공약수가 1일 때 두 수는 서로소이기 때문에 최대공약수를 구해 1인지 판별하였다.

 

유클리드 호제법

출처 : https://www.youtube.com/watch?v=TxdljAFjTNw

 

 

참고자료

더보기
유클리드 호제법의 원리