개발일지/Algorithm
백준 1등 - 14252 공약수열 [수학]
14252번: 공약수열 서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘 www.acmicpc.net 간단 요약 해당 문제는 배열 A가 주어지면 해당 배열을 오름차순 정렬하여, 인접한 수들의 최대공약수가 1이 되도록 숫자를 추가하고, 몇 개가 추가돼야 하는지 그 개수를 리턴하면 됩니다. 접근 방법 추가될 숫자를 찾는 것이 아닌, 추가될 숫자의 개수만 구하면 됩니다. 문제의 핵심은 모든 수는 인접한 수를 최대공약수 1로 만들려면 1개 또는 2개로 해결이 됩니다. 해당 문제는 이 개념을 아느냐 모르느냐로 난이도가 결정되는 듯한데, 증명하는 방법은 잘 모르겠습니다. ..
