[백준] 14252번 공약수열 문제풀이

 

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

14252번: 공약수열

<문제설명>

문제)

서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘으면 안 된다. 그러기 위해서 수를 최소 몇 개 추가해야하는지 구하는 프로그램을 작성하시오.

입력)

첫째 줄에 N이 주어진다.(1 <= N <= 50)

둘째 줄에는 집합에 포함되어 있는 수가 주어진다. 주어지는 수는 100,000보다 작거나 같은 자연수이다.

출력)

첫째 줄에 수를 최소 몇 개 추가해야하는지 출력한다.

예제 입력 1)

4
2200 42 2184 17

예제 출력 1)

3

예제 입력 2)

5
13 1 6 20 33

예제 출력 2)

0

예제 입력 3)

2
7 42

예제 출력 3)

1

<아이디어>

a와 b사이에 몇 개의 수를 넣어야 공약수열을 만족하는지 확인해주는 함수를 만들어야 한다고 생각했다.

함수의 작동방식은 다음과 같다.

 

인접한 두 수 a와 b의 최대공약수가 1인지 아닌지 확인한다.

1이라면 0을 리턴한다. 1이 아니라면 a와 b사이에 몇 개의 수를 넣어야 하는지 확인해야 한다.

a+1과 b 사이의 한 정수를 i라고 하자. a와 i, b와 i의 최대공약수가 각각 모두 1이라면 1을 리턴한다.

두 경우를 모두 만족하지 못한다면 2를 리턴한다.

 

배열을 입력받고 정렬시킨 후 위와 같은 함수를 작동시키면 ans에 그 값이 더해져 답을 도출할 수 있을 것이다.

아래는 이를 구현한 소스코드이다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n,ans,v[51];
int gcd(int a, int b)//유클리드 호제법
{
    return b?gcd(b,a%b):a;
}
int check(int a, int b)//공약수 확인 함수
{
    if(gcd(a,b)==1) return 0;  //a와 b의 최대공약수가 1이라면 0반환 
    for(int i=a+1;i<b;i++)
        if((gcd(a,i)==1)&&(gcd(i,b))==1) return 1; //a와 i, b와 i의 최대공약수가 각각 모두 1이라면 1반환
    return 2; //모두 만족하지 않을 때 2반환
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&v[i]);
    sort(v,v+n);
    for(int i=0;i<n-1;i++) ans+=check(v[i],v[i+1]);
    printf("%d",ans);
}