👀 문제
https://www.acmicpc.net/problem/9613
👊 도전
1. 설계
- 입력받은 수의 모든 경우의 수에 따라 GCD를 구한다.
2. 구현 (성공 코드)
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
31
32
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
public static int gcd(int a, int b) {
if(a%b==0) return b;
else return gcd(b, a%b);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
int t=scan.nextInt();
for(int i=0;i<t;i++) {
int n=scan.nextInt();
int[] array=new int[n];
for(int j=0;j<n;j++) {
array[j]=scan.nextInt();
}
long sum=0;
for(int j=0;j<n;j++) {
for(int k=j+1;k<n;k++) {
sum+=array[j]>array[k]? gcd(array[j], array[k]):gcd(array[k], array[j]);
}
}
System.out.println(sum);
}
}
}
3. 결과
🤟 성공 🤟
sum은 int형을 벗어날 수 있으므로 long으로 선언해주어야 한다.
4. 설명
- 각 테스트 케이스마다 가능한 모든 쌍을 구한다
- 2중for문을 돌려 모든 경우의 수를 구한다.
- GCD를 구한다
- a%b==0이 될때까지 재귀호출하는 방식으로 최대공약수를 구한다.