백준) 14232 보석도둑 파이썬 풀이 및 시간복잡도 생각

보석 도둑

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

1984

539

396

27.634%

문제

희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개 훔쳐갈 시, 보석끼리 달라붙으며 무게가 모든 보석들의 곱으로 늘어난다.

효빈이는 이 보안장치를 해제할 수 없기 때문에, 차라리 곱해진 대로 최대한 많은 보석들을 가져오기로 계획했다. 효빈이는 한번에 k라는 무게를 들 수 있으므로, 딱 k만큼의 무게만큼의 보석을 가져오고 싶은데, 그 때 보석들의 최대 개수를 알고싶다.

영선상에는 세계 최고의 보석가게답게 모든 무게의 보석들이 매우 많이때문에, 훔쳐가는 보석이 부족할 일은 없다. 다만 모든 보석들은 무게가 1보다 크다.

효빈이는 이제 영선상에 잡입할 계획을 다 세웠다. 하지만 무슨 보석들을 훔쳐올지 결정하지 못하였는데, 효빈이를 대신하여 훔쳐올 보석들을 결정해주자.

입력

첫째 줄에는 효빈이가 들 수 있는 무게 k가 주어진다.(2≤k≤1012)

출력

첫째 줄에는 효빈이가 훔쳐올 보석의 개수를 출력하고, 다음 줄에는 훔쳐올 보석들의 무게를 오름차순으로 출력하시오.

예제 입력 1 복사

15

예제 출력 1 복사

2
3 5

 

 

내가 풀었던 풀이 

import sys
input=sys.stdin.readline
jewel=int(input())
ans_list=[]
stop=False
while(True):
    half=int(jewel**0.5)
    for i in range(2,half+1):
        if jewel%i==0:
            ans_list.append(i)
            jewel=jewel//i
            break
        if i==half:
            stop=True
            ans_list.append(jewel)
    if stop==True:break

print(len(ans_list))
print(*ans_list)

최대한 많은 보석을 원한다고 하였으므로 보석의 무게를 소인수분해하면 된다고 생각하였다.

근데 나는 소인수분해 하는 방법을 몰랐어서 약수가 나올 수 있는 수까지인 2부터 보석의 크기의 루트까지 탐색

for i in range (2, jewel**0.5)  하고, 그 중 jewel%i==0이 되는 수로 나누어주는 것을 반복하였다.

시간복잡도는 O(sqrt(n))이겠지만, 최악의 상황에 아래의 코드보다 조금 더 반복 할 수도 있으므로 성능이 나쁜 코드이다.

아래는 내가 보고 학습한 모범 풀이이다.

 

 

모범 풀이

from math import sqrt,ceil

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

for i in range(2, ceil(sqrt(k))):
    while k%i == 0:
        j.append(i)
        
        k //= i    
       
if k != 1: j.append(k)

print(len(j))
print(*j)

for문 안에 보석무게%i==0이 될때에만 append를 하게 해준 멋진 코드이다.

이렇게 하면 아무리 많이 반복해도 sqrt(k)회 이상 반복하지 않는다.

 

오늘의 배운점

리스트의 값들을 공백을 두고 출력하려면 print(*리스트 이름) 이라고 하면 된다.

소인수분해를 하는 멋진 코드가 있다.