[알고리즘] 백준 9631번 문제 GCD 합

백준 9631번 문제를 풀어봤다.

 

 

문제는 다 풀어놓고, 출력형식이 one by one으로 입력 한줄당 출력되는걸 모르고,

enter가 밀린다고 생각하며 40분을 해메는 멍청이가 여깄습니다....

 

이전 유클리드 호제법을 이용해 풀었던 문제와 패턴은 동일해서, 어떤식으로 입력을 받을지 어떻게 저장해서 출력할지에 대해 고민하고 문제를 풀었다.

 

다음은 범위에 대한 고민인데, 다른 분 블로그에서 펌해왔다.

 

- n이 1 ~ 100의 범위이고, n개의 수의 범위는 1 ~ 1,000,000인데,

- n개인 수들을 2개씩 짝지어 만드는 모든 경우의 수는 n(n-1) / 2 이다.
- 그러면 이 짝에서 n(n-1) / 2개의 최대공약수들이 나오는데 그 수는 1 ~ 1,000,000의 범위를 가 지므로 총 합의 최대범위는 100*99 / 2 * 1,000,000 = 4,950,000,000(49억)이다.
- 이는 int형의 표현범위 +-21억 을 넘고, unsigned int형의 표현범위 +42억을 넘어서는 값으로
- long long 형을 사용해야 한다.(long long 형의 저장범위는 +-900경)
(출처 : https://ldgeao99.tistory.com/298)

[JAVA 구현코드]

package step_by_step;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Quiz_9613 {
 
    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(st.nextToken());
        long count = 0; //반드시 long으로 해야 정답!
 
        for(int i=0; i<N; i++){
            String input[]=br.readLine().split(" ");
            count =0;
            for(int k=1; k<input.length; k++) {
                for (int j = k+1; j < input.length; j++) {
                    count += gcm(Math.max(Integer.parseInt(input[k]), Integer.parseInt(input[j])), Math.min(Integer.parseInt(input[k]), Integer.parseInt(input[j])));
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb.toString());
 
    }
    public static int gcm(int big, int small){
 
        while(small>0){
            int r = big%small;
            big=small;
            small=r;
        }
        return big;
 
    }
}