# [Platinum V] 공약수열 [문제 링크](https://www.acmicpc.net/problem/14252) ## 문제 설명 <p>서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘으면 안 된다. 그러기 위해서 수를 최소 몇 개 추가해야하는지 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)</p> <p>둘째 줄에는 집합에 포함되어 있는 수가 주어진다. 주어지는 수는 100,000보다 작거나 같은 자연수이다.</p> ## 출력 <p>첫째 줄에 수를 최소 몇 개 추가해야하는지 출력한다.</p> ## 풀이 #### 두 수 사이에는 최대 2개의 수를 집어넣으면 됩니다. 이 사실을 모르더라도, 수의 범위가 작아서 직접 수를 넣어보며 풀 수 있습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> v(n); for(int i=0;i<n;i++) cin >> v[i]; sort(v.begin(), v.end()); int cnt=0; for(int i=0;i<v.size()-1;i++) { if(gcd(v[i], v[i+1])!=1) { int notGcd=2, minVal = v[i]+1; for(int j=v[i]+1;j<v[i+1];j++) { int curNotGcd = (gcd(v[i], j)!=1) + (gcd(j, v[i+1])!=1); if(notGcd>curNotGcd) { notGcd = curNotGcd; minVal = j; } } if(notGcd==0) cnt++; else cnt += 2; } } cout << cnt; } ```