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

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

14232번: 보석 도둑

 

코드

from math import sqrt,ceil

k = int(input())

j = []

for i in range(2, ceil(sqrt(k))+ 1):

    while k%i == 0:

        j.append(i)

        k //= i    

       

if k != 1: j.append(k)

print(len(j))

print(*j)

 

풀이과정

우선, 문제만 봤을 땐 어떻게 풀어야 할지 잘 감이 안오고, 또 뭔가 소수로 풀어야 할 거 같은 느낌이 들지만 사실 소인수 분해 알고리즘으로 아주 간단하게 풀수 있는 문제였다. 코드도 정말 간단해서 사실 모르면 한없이 어렵지만 알고보면 정말 쉬운 문제가 아닐수 없었다.