개요
백준 문제 9613번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 10분
https://www.acmicpc.net/problem/9613
문제
양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.
코드
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <iostream>
using namespace std;
const int MAX = 100;
int GCD(int numA,int numB)
{
if(numA < numB)
{
int tmp = numA;
numA = numB;
numB = tmp;
}
while(numB != 0)
{
int r = numA % numB;
numA = numB;
numB = r;
}
return numA;
}
void solve()
{
int testCase;
int numArr[MAX];
fill_n(numArr,MAX,0);
cin >> testCase;
for(int i=0;i<testCase;i++)
{
int N = 0;
long long sum = 0;
cin >> N;
for(int j=0;j<N;j++)
{
cin >> numArr[j];
}
for(int k=0;k<N;k++)
{
for(int l=k+1;l<N;l++)
{
sum += GCD(numArr[k],numArr[l]);
}
}
cout << sum << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}
|
풀이
쌍이라길래 중복되는 부분을 없애주어야하나 생각을 했는데 그렇진 않은 것 같다.
그냥 무지성 GCD,LCM으로 풀면 됨
배운 점
1
2
3
| ios_base::sync_with_stdio(0);
cin.tie(0);
//속도 향상에 도움됨 쓰는 습관 기르기
|