개발일지/Algorithm
백준 1등 - 14252 공약수열 [수학]
E-room
2023. 9. 20. 11:09
728x90
14252번: 공약수열
서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘
www.acmicpc.net
간단 요약
해당 문제는 배열 A가 주어지면 해당 배열을 오름차순 정렬하여,
인접한 수들의 최대공약수가 1이 되도록 숫자를 추가하고,
몇 개가 추가돼야 하는지 그 개수를 리턴하면 됩니다.
접근 방법
추가될 숫자를 찾는 것이 아닌, 추가될 숫자의 개수만 구하면 됩니다.
문제의 핵심은 모든 수는 인접한 수를 최대공약수 1로 만들려면 1개 또는 2개로 해결이 됩니다.
해당 문제는 이 개념을 아느냐 모르느냐로 난이도가 결정되는 듯한데, 증명하는 방법은 잘 모르겠습니다.
어떤 분이 남긴 글을 보았는데, 사실 봐도 잘 이해 안 가긴 합니다.
문제는 풀었지만, 정답은 맞추지 못한 느낌...?
정수론 강의 14252문제 - 인프런 | 질문 & 답변
왜 두 수 사이에 3개 이상은 불가능한지 귀납법으로 어떻게 증명할지를 모르겠어서 질문 남깁니다. - 질문 & 답변 | 인프런
www.inflearn.com
- 주어진 배열을 오름차순으로 정렬한다.
- 인접한 두 수를 검사하여 최대공약수가 1인지 확인한다.
- 1이 아닐 경우 A~B까지 돌며 gcd(A, n) == 1, gcd(n, B) == 1을 만족하는 숫자가 존재하는지 검사한다.
- 존재한다면 정답에 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;
}
}
깃허브 전체 코드
728x90