백준 14252 공약수열 파이썬 문제풀이 (python 정수론 최적화)

문제 보러가기

 

 

백준 공약수열 파이썬 문제풀이

공약수 gcd 기법을 이용하는 문제이지만 상당히 어려운 문제이다.

 

주어진 수들을 나열했을 때 인접 두 수가 서로소가 되도록 

중간에 수를 추가하는데, 몇 개를 추가해야하는지 구하는 문제이다.

 

중간에 들어가는 수가 반드시 하나라는 법이 없기 때문에 서로 비교하는 방법이 헷갈린다.

 

우선 단순히 접근해서 로직을 만들었다.

 

인접한 두 수 a,b가 있고 그 사이에 들어가는 수를 c라고 한다.

 

gcd(a,b) == 1이면 넣으면 되고,

 

그게 아니라면

gcd(a,c) == 1이면서 gcd(c,b) == 1인 값을 찾는다.

없다면 gcd(a,c) == 1만 만족하는 수를 넣고 gcd(d,b)를 시도한다.

 

이 로직을 염두하고 코드를 짜보자.

def gcd(a,b):
    while a%b!=0:
        tmp = a%b
        a=b
        b=tmp
    return b

N = int(input())
number = list(map(int, input().split()))
number.sort()
cnt=0
i = 0
checkAppend = False
while i < N-1:
    checkAppend = False
    gcdRes = gcd(number[i], number[i+1])
    if gcdRes != 1:
        # gcd(a,c) = 1이면서 gcd(c,b) = 1인 값 탐색
        for between in range(number[i]+1,number[i+1]+1):
            if gcd(number[i], between) == 1 and gcd(between, number[i + 1]) == 1:
                number.insert(i+1,between)
                N += 1
                cnt += 1
                checkAppend = True
                break
        if between == number[i+1] and checkAppend == False: # 없으면
            for between in range(number[i] + 1, number[i + 1]+1):
                if gcd(number[i], between) == 1:
                    number.insert(i+1, between)
                    N += 1
                    cnt += 1
                    checkAppend = True
                    break
    i+=1
    if checkAppend == True:
        i=0
print(number)

열심히 짰지만 예제를 통과하지 못했다...

중간에 들어갈 수가 2개가 되는 경우는 어떻게 처리해야하나..

 

발상의 전환

위에서 a,b,c로 비교를 했을 때

gcd(a,c) == 1 이면서 gcd(c,b) == 1인 값이 없다면 

일단 1개의 값으로는 충분하지 않다는 것

 

중간의 들어갈 수가 1개가 아니라면, 몇 개까지 가능할까?

정확히 이걸 증명하기는 어렵지만, 수학적으로 최대 2개까지 들어갈 수 있다고 한다.

 

그렇다면 " gcd(a,c) == 1 이면서 gcd(c,b) == 1인 값이 없다"의 상황에서

2개를 카운트하면 된다는 말이다.

 

물론, 사이에 들어갈 수가 최대 2개라는 것을 증명한다는 것은

이 문제를 푸는 것보다 어려울 수 있다.

 

하지만 정말 수학적으로 똑똑하지 않다면 문제를 보고

증명하진 않았지만 이렇게 규칙이 있지 않을까? 하는

 

센스를 발휘하는 방법도 있다고 생각한다.

코딩테스트는 증빙이 중요한게 아니기 때문에...

 

코드

그럼 코드에 적용해보자.

def gcd(a,b):
    while a%b!=0:
        tmp = a%b
        a=b
        b=tmp
    return b

N = int(input())
number = list(map(int, input().split()))
number.sort()
cnt=0
i = 0
checkAppend = False
while i < N-1:
    checkAppend = False
    gcdRes = gcd(number[i], number[i+1])
    if gcdRes != 1:
        # gcd(a,c) = 1이면서 gcd(c,b) = 1인 값 탐색
        for between in range(number[i]+1,number[i+1]):
            if gcd(number[i], between) == 1 and gcd(between, number[i + 1]) == 1:
                number.insert(i+1,between)
                N += 1
                cnt += 1
                checkAppend = True
                break
        if between == number[i+1]-1 and checkAppend == False: # 없으면
            cnt += 2
    i+=1
    if checkAppend == True:
        i=0
print(cnt)

 

 

위 코드에서 between이 gcd가 number[i], number[i+1]를 모두 만족하지는 않는 경우,

두 개가 필요한 것이므로 카운트를 2추가하게 했다.

 

하지만 틀렸다. 50%까지는 채점이 되었다.

 

틀린 부분은 유심히 찾아보니

append하면서 찾는 방식이 잘못된 것 같다.

중간에 append로 list값이 달라지면서 갯수를 잘못 세는 것이다.

 

정답 코드

def gcd(a,b):
    while a%b!=0:
        tmp = a%b
        a=b
        b=tmp
    return b

N = int(input())
number = list(map(int, input().split()))
number.sort()
cnt=0
i = 0
checkAppend = False
while i < N-1:
    checkAppend = False
    gcdRes = gcd(number[i], number[i+1])
    if gcdRes != 1:
        # gcd(a,c) = 1이면서 gcd(c,b) = 1인 값 탐색
        for between in range(number[i]+1,number[i+1]):
            tmp = 0
            if gcd(number[i], between) == 1:
                tmp+=1
            if gcd(between, number[i + 1]) == 1:
                tmp+=1
            if tmp > 1:
                cnt += 1
                break
            if between == number[i+1] - 1:
                cnt += 2
    i+=1
print(cnt)

코드가 더러워지긴 했는데, 배열에 append하지 않는 방법으로 수정했다.

gcd가 i와 i+1 양쪽 다 나오면 cnt 1개

끝까지 안나온다면 cnt 2개를 추가하는 식이다.

 

 

이렇게 했더니 정답이었다!

중요한 것은 list를 수정하지 않고 그대로 사용하는 점과  between == number[i+1] - 1 조건이었다.