[백준(JAVA)] 9613번: GCD 합

세하·2025년 5월 5일

[백준] 문제풀이

목록 보기

51/94

설명

GCD : 최대공약수 구하기
유클리드 호제법 사용 :
큰 수(a)를 작은 수(b)로 나누면서 나머지를 구하고, 그 나머지가 0이 될때까지 작은수(a)와 그 나머지(b)를 다시 나눈다. 나눈 나머지가 0이 된다면 a가 GCD가 된다.

그러나 두 수의 순서에 영향을 받지 않으니 꼭 a에 큰 수, b에 작은 수를 넘겨야하는건 아니다.
처음에 Math.max, Math.min을 사용하여 구분지어 넘겨줬는데 오히려 이 연산이 성능을 소폭 떨어뜨릴 수 있다.

증명 :

getGCD(2, 10); // 2가 작음
// a=2, b=10
// temp = 2 % 10 = 2
// a = 10, b = 2
// temp = 10 % 2 = 0
// 종료 → GCD는 2
getGCD(10, 2); // 10이 큼
// a=10, b=2
// temp = 10 % 2 = 0
// 종료 → GCD는 2

결과는 동일

처음에 푼 풀이 (틀림)

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

public class Main2 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int t = Integer.parseInt(br.readLine());

        int n;
        StringTokenizer st;
        ArrayList<Integer> list = new ArrayList<>();
    
        for (int i = 0; i < t; i++){
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            //while (st.hasMoreTokens()) 은 불확실성을 유발하므로 n만큼 for문으로 직접 읽는 게 명확
            while(st.hasMoreTokens()){
                list.add(Integer.parseInt(st.nextToken()));
            }

            int sum = 0;
            for (int j = 0; j < n - 1; j++){

                for (int k = j + 1; k < n; k++){
                    sum += getGCD(Math.max(list.get(j), list.get(k)), Math.min(list.get(j), list.get(k)));
                }
            }

            if (i < t - 1){
                sb.append(sum).append("\n");
            } else {
                sb.append(sum);
            }

            list.clear();
        }

        System.out.print(sb);
    }

    //무조건 a에 큰 수가 들어오고 b에 작은 수가 들어오게 품
    public static int getGCD(int a, int b){
        // System.out.println(a + " " + b);
        int num = a % b;
        // System.out.println(num);
        if (num != 0){
            return getGCD(Math.max(num, b), Math.min(num, b));
        } else {
             return b;
        }
    }
}

틀린 이유

분명 IDE에서 실행시켜봤을때는 잘 실행되었다. 그런데 왜 틀렸다고 나왔을까? 각 테스트케이스에서 한 줄에 수의 개수를 입력받고 그 뒤에 바로 n개의 수가 주어진다. 그 한 문자열을 나는 StringTokenizer로 나누고 첫 토큰을 n에 대입하고 그 이후부터는 .hasMoreTokens()를 활용하여 list에 add해주었다.
그러나 이는 불확실성을 유발할 수 있다.
나는 ArrayList를 for문 바깥에 선언하고 GCD 연산이 끝난 이후 맨 마지막에 clear()를 통해서 list를 비워주었다. 이게 문제가 되었다. list가 이전 값들을 잘못 유지하거나, 오류를 발생시킬 수 있다. st.hasMoreTokens()이 예상보다 일찍 끝나거나,
중간에 Integer.parseInt()가 예외를 던지면 list는 clear() 전에 이미 잘못된 상태가 된다.
🚨 이러한 버그는 IDE에서는 특정 입력에서는 발견되지 않고, 채점 시스템에서만 발견될 수 있다.
💡 따라서 매 테스트케이스마다 list를 새로 만들고, .hasMoreTokens()를 사용하기보다는 for문을 통해 정확히 n의 갯수만큼 돌려주는게 안전하다.

풀이

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

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

        int n;
        StringTokenizer st;
    
        for (int i = 0; i < t; i++){
            //매번 새로 생성
            ArrayList<Integer> list = new ArrayList<>();

            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            //확실하게 n개 읽음
            for (int j = 0; j < n; j++){
                list.add(Integer.parseInt(st.nextToken()));
            }

            //합이 클 수도 있으니까 long 사용
            long sum = 0;
            for (int j = 0; j < n - 1; j++){

                for (int k = j + 1; k < n; k++){
                    //넘기는 수의 순서 고려 안해도 됨
                    sum += getGCD2(list.get(j), list.get(k));
                }
            }

            if (i < t - 1){
                sb.append(sum).append("\n");
            } else {
                sb.append(sum);
            }
        }

        System.out.print(sb);
    }

    public static int getGCD(int a, int b){
        while (b != 0){
            int tmp = a % b;
            a = b;
            b = tmp;
        }

        return a;
    }

    public static int getGCD2(int a, int b){
        if (b == 0){
            return a;
        }

        return getGCD2(b, a % b);
    }
}