공부 110일차: 백준 9613번 GCD 합 자바 java

9613 GCD 합

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

9613번: GCD 합

 

 

 

---

백준 9613번 문제 GCD 합

---

문제

---

 

 

 

 

---

과정 생각해보기

---

https://gimbalja.tistory.com/173

공부 94일차: 백준 2609번 최대공약수와 최소공배수 자바 java

gcd를 최대공약수로, 위의 링크에 유클리드 호제법으로 간단하게 최대공약수를 구현하는 방법을 설명해두었다

 

 

모든 쌍을 구해야 한다는 말도 한 번 살펴볼 필요가 있다

10, 20, 30, 40 → [10,20] [10,30] [10,40] [20,30] [20,40] [30,40]

즉, 자신의 오른쪽에 있는 모든 숫자와 쌍을 이루면 된다

 

 

1. 최대공약수 gcd를 구하는 메서드를 만든다

2. testcase만큼 도는 반복문

　2-1. 각 테스트 케이스 맨앞에 있는 n을 뽑는다

　2-2. n만큼 반복문을 돌려 ArrayList에 숫자를 넣는다

　2-3. 이중for문을 활용해 자신의 오른쪽에 있는 모든 숫자들과 gcd 메서드를 돌리고 더할 수 있도록 한다

 

 

*주의사항: sum이 int의 최대값을 넘어갈 수 있으므로 long 타입으로 선언한다

모든 값을 최대로 설정했을 때, 답은 49.5억이 나오기 때문이다

자세한 최대값 확인 과정은 아래 블로그를 참고했다

https://wonit.tistory.com/414

 

 

 

---

정답 인정 코드

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st; 
        
        int t = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < t; i++) {
            // 줄마다 초기화하기 위해 ArrayList 객체를 반복문 안에 생성
            ArrayList<Integer> list = new ArrayList<>();
            st = new StringTokenizer(br.readLine());
            
            int n = Integer.parseInt(st.nextToken());
            for(int j = 0; j < n; j++) {
                list.add(Integer.parseInt(st.nextToken()));    //숫자 넣기
                // 디버깅
                //System.out.print(list.get(j)+" ");
            }
            
            
            long sum = 0;    //int 범위 넘어설 수 
            for(int j = 0; j < list.size() - 1; j++) {
                for(int k = j+1; k < list.size(); k++) {
                    sum += gcd(list.get(j), list.get(k));
                }
            }
 
            System.out.println(sum);
            
        }
 
    }
    
    // 최대공약수
     public static int gcd(int x, int y) {
        if(y == 0) {
            return x;                
        }else {
            return gcd(y, x%y);                
        }
    }
 
}
 

 

과정에서 글로만 설명하다 보니 조금 난해해보일 수 있지만, 코드를 보면 쉽게 이해할 수 있을 것이다

 

 

 

---