[백준] 14252번 공약수열

사용 언어 - Python3

문제 -  14252번 공약수열

14252번: 공약수열

 

 

정답

최대공약수 GCD(A,B) (정답 맞춘 여부 X)

arr 한개씩 확인하면서 두 값 사이에 gcd 최대공약수가 있다면, 몇개의 값이 필요한지 검사한다.

a+1부터 b까지 for문 반복하면서, 

gcd(a,j) 또는 gcd(b,j) 최대공약수가 존재한다면, tmp += 1, count += 1

최대공약수 존재하지 않고 for문이 끝났다면, count += 2

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split()))) # 정렬

# 최대공약수 함수
def gcd(a,b):
    while a % b != 0:
        tmp = a % b
        a = b
        b = tmp
    return b

count = 0 # 총 횟수
arr2 = [] # 검사필요한 arr 저장

for i in range(len(arr)-1):
    if gcd(arr[i],arr[i+1]) > 1: # 최대공약수 있다면,
        arr2.append([arr[i],arr[i+1]]) # arr 값 저장

for a, b in arr2:
    for j in range(a+1,b):
        tmp = 0
        # a또는 b와 최대공약수인 값이 있다면, tmp += 1
        if gcd(a, j) == 1 : tmp += 1
        if gcd(b, j) == 1 : tmp += 1

        # 최대공약수 한개로 해결 가능 -> count = 1
        if tmp > 1:
            count += 1
            break

        # 최대공약수를 못찾고 for문이 끝났다면, 2개 추가해야함
        if j == b -1 :
            count += 2

print(count)

 

레퍼런스

• 정답 깃허브https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/14252_%EA%B3%B5%EC%95%BD%EC%88%98%EC%97%B4.py