백준 14232 보석 도둑 파이썬 문제풀이 (python 정수론 최적화)

문제 보러가기

 

 

백준 보석 도둑 파이썬 문제풀이

k 무게만큼의 보석을 가져오고 싶은데, 보석들의 무게는 서로 곱해진다고 한다.

정해진 k무게 안에서 가장 많은 보석을 가져올 수 있는 개수를 구하는 문제이다.

k는 \( 2≤k≤10^{12}\) 이다.

 

주의할 점은 k에 딱 맞게 가져온다는 점.

그렇다면 떠오르는 것은?

 

소인수분해

공약수끼리 곱해서 정확히 k가 되도록 해야한다.

그러면서도 가장 많은 나누어야한다. 소인수분해가 적당하다.

 

소인수분해는 단순히 2,3,4 이런식으로 나누어서 구할 수 있다.

하지만 k의 최대값을 보면 절대 안될 것이다.

 

흠.. 하지만 다른 방안이 생각나지 않는다.

 

가장 작은 숫자 2부터 시작해서 나눠지는 값을 찾으면

우선 나누고 그 몫을 다시 2부터 나눠보는 단순 연산으로 일단 해보자.

k = int(input())
weights = []

def divideVal(val):
    for i in range(2,val+1):
        if val % i == 0:
            weights.append(i)
            divideVal(val // i)
            break

divideVal(k)
print(len(weights))
for i in weights:
    print(i,end=" ")

결과는 예상대로 시간 초과

 

시간 줄이기

마냥 소인수로 계속 나누는게 아니라. 

약수의 중간 지점을 찾아야한다.

 

중간이 되는 약수는 보통 제곱근으로 구할 수 있다는 점을 알아야한다.

그러면 재귀의 로직을 제곱근을 이용한 로직으로 바꿀 수 있다.

import math

k = int(input())
weights = []
def rootVal(val):
    # 소수인지 체크

    weights.append(val)

    # 아니라면
    root = int(math.sqrt(val))
    rootVal(root) # root * val//root = val
    rootVal(val // root)

rootVal(k)
print(len(weights))
for i in weights:
    print(i,end=" ")

여기서 소수인지 체크를 하고 

소수라면 weights에 넣으면 될 것 같다.

 

소수인지 빠르게 체크를 하는 방법은 메모리를 좀 써서 에라토스테네스의 체를 만드는 방법이 있다.

쉽게 말해서 소수 리스트를 만들어서 포함되는지 체크하는 것이다.

 

음.. 위 로직은 좀 잘못된 것 같다.

 

나누는 수를 증가시키기

말그대로 가장 작은 소인수인 2로 최대한 나눈 후, 3으로 최대한 나누고

이런식으로 하나씩 증가시키며 나누는 방법이다.

 

이미 가장 작은 소인수로 나누었기 때문에 나누는 수를 증가시켜도

나눠지는 수는 소수로 나눠질 것이다.

코드에서 나누는 수는 divider를 말한다.

 

import math

k = int(input())
weights = []
remain = k
divider = 2

while remain != 1:
    while remain % divider == 0:
        remain //= divider
        weights.append(divider)
    divider+=1

print(len(weights))
for i in weights:
    print(i,end=" ")

이래도 시간 초과가 나온다.

 

정답 코드

k = int(input())
weights = []
remain = k

divider = 2
while remain % divider == 0: # 2로 모두 나누기
    remain //= divider
    weights.append(divider)

divider = 3
while divider * divider <= remain: # 제곱수가 절반 크기의 약수와 가장 가까움
    while remain % divider == 0:
        remain //= divider
        weights.append(divider)
    divider+=2

if remain > 1 : # 제곱수까지 홀수들이 안나눠지면 남은 값은 소수임
    weights.append(remain)

print(len(weights))
for i in weights:
    print(i,end=" ")

 

쉽지 않았다.

결국 절대적인 로직이 있던 것보단 시간을 최대한 줄이기 위한 방법을 써는 방향이었다.

 

에라토스테네스의 체를 찾는게 아니라

일단 2로 모두 나누어서 짝수를 배제하고

 

남은 수는 홀수들로 차근차근 나눈다.

이때 k의 제곱근보다 작은 값까지만 진행하는 것이 요점이다.

k가 \(10^{12}\)이기 때문이다.

 

그리고 제곱근보다 작은 홀수까지 나누었는데도 남았다면 그건 소수이기에 추가하는 방식이다.