[BOJ][C++] 백준 9613번 GCD 합
Updated:
9613번 GCD 합
1. 문제 정보
백준 온라인 저지 [9613번 GCD 합] 문제의 링크입니다.
문제
양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.
출력
각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.
예제 입력1
3
4 10 20 30
40 3 7 5 12
3 125 15 25
예제 출력1
70
3
35
시간 / 메모리 제한
1초 / 128MB
2. 생각
- 지난 번에 푼 문제 2609번 최대공약수와 최소공배수가 떠올랐습니다. 그러나 그 문제에서 푼 방법은 단순히 나누어지는지 확인했기 때문에 O(N)의 시간복잡도를 가진 알고리즘이었습니다.
-
그러나 이 문제에서는 테스트케이스(T)와 숫자의 개수(N)이 각각 100이하의 자연수이고, n의 범위는 1,000,000입니다.
대략적으로 시간을 계산해봤을 때 100 * 100 * 1,000,000 = 10,000,000,000이므로 시간제한인 1초를 넘습니다.(대략 1억=1초)
따라서, 다른 알고리즘으로 풀어야합니다. - 유클리드 호제법을 이용합니다. 여기서 호제법이란 두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는 방법입니다.
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(단, a> b), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
wiki/유클리드_호제법
a와 b의 최대 공약수를 (a, b)라고 하면, (a, b) = (b, r)이다.
예 1) 1071, 1029 (1071, 1029) = (1029, 42) = (42, 21) = (21, 0)
예 2) 10 30 (10, 30) = (30, 10) = (10, 0) = 10
예 3) 7 5 (7, 5) = (5, 2) = (2, 1) = (1, 0) = 1
예 4) 15, 25 (15, 25) = (25, 15) = (15, 10) = (10, 5) = (5, 0) = 5
- 프로그래밍으로 구현할 때는 재귀를 이용하거나 반복문을 통해 구현할 수 있습니다.
저는 반복문을 통해 구현해보겠습니다.
3. 소스코드 (C++)
