백준 1등 - 14252 공약수열 [수학]

 

14252번: 공약수열

의도한건 아닌데 파이썬 1위 했습니다 ㅋㅋ

간단 요약

해당 문제는 배열 A가 주어지면 해당 배열을 오름차순 정렬하여,

인접한 수들의 최대공약수가 1이 되도록 숫자를 추가하고,

몇 개가 추가돼야 하는지 그 개수를 리턴하면 됩니다.

 

접근 방법

추가될 숫자를 찾는 것이 아닌, 추가될 숫자의 개수만 구하면 됩니다.

 

문제의 핵심은 모든 수는 인접한 수를 최대공약수 1로 만들려면 1개 또는 2개로 해결이 됩니다.

해당 문제는 이 개념을 아느냐 모르느냐로 난이도가 결정되는 듯한데, 증명하는 방법은 잘 모르겠습니다.

어떤 분이 남긴 글을 보았는데, 사실 봐도 잘 이해 안 가긴 합니다.

문제는 풀었지만, 정답은 맞추지 못한 느낌...?

정수론 강의 14252문제 - 인프런 | 질문 & 답변

 

1. 주어진 배열을 오름차순으로 정렬한다.
2. 인접한 두 수를 검사하여 최대공약수가 1인지 확인한다.
3. 1이 아닐 경우 A~B까지 돌며 gcd(A, n) == 1, gcd(n, B) == 1을 만족하는 숫자가 존재하는지 검사한다.
4. 존재한다면 정답에 1, 존재하지 않으면 2를 더한다.

 

파이썬

def gcd(a: int, b: int):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def check(a: int, b: int):
    for i in range(a + 1, b):
        if gcd(a, i) == 1 and gcd(i, b) == 1:
            return 1
    return 2

n = int(input())
arr = list(map(int, input().split()))
arr.sort()

answer = 0
for i in range(n - 1):
    if gcd(arr[i], arr[i + 1]) != 1:
        answer += check(arr[i], arr[i + 1])
print(answer)

 

자바

public class Main {
    public static void main(String[] args) {
        // 입력처리
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        // 풀이시작
        int answer = 0;
        for (int i = 0; i + 1 < arr.length; i++) {
            if (gcd(arr[i], arr[i + 1]) != 1) {
                answer += check(arr[i], arr[i + 1]);
            }
        }
        System.out.println(answer);
    }

    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    static int check(int a, int b) {
        for (int i = a + 1; i < b; i++) {
            if (gcd(a, i) == 1 && gcd(i, b) == 1) {
                return 1;
            }
        }
        return 2;
    }
}

 

깃허브 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Platinum/14252.%E2%80%85%EA%B3%B5%EC%95%BD%EC%88%98%EC%97%B4