[백준/Python] 14232. 보석도둑

 

 

1. 백준 14232. 보석도둑(실1)

https://www.acmicpc.net/problem/14232

14232번: 보석 도둑

풀이

 

CODE

import sys

input = sys.stdin.readline


def prime_factorization(n):
    i = 2
    ans_list = []
    while i * i <= n:  # n 값 업데이트 기준
        if n % i:  # 나머지가 있으면 현재 i 값으로 안 나눠지므로 i값 증가시킴
            i += 1
        else:
        	# 현재 i 값으로 나눠지므로 n update & ans_list append
            n //= i
            ans_list.append(i)
    # while 문 탈출하고 남은 n은 더이상 나눠지지 않는 수 -> ans_list에 append
    if n > 1:
        ans_list.append(n)

    return ans_list


num = int(input())
answer = prime_factorization(num)
print(len(answer))  # 효빈이가 훔칠 총 보석 수의 최댓값
for a in answer:
	# 효빈이가 훔친 보석 각각의 무게(이미 오름차순으로 정렬되어 있음)
    print(a, end=' ')

• 처음에 에라토스테네스의 체로 푸는 줄 알고 시도했다가 메모리초과 발생
• 다음 번엔 메모리초과 상황도 신중히 고려해야겠다.