[PS] BOJ 14232 / 보석 도둑

Minjun Kim

16 May 2025 • 1 min read

문제 링크: https://www.acmicpc.net/problem/14232

Thumbnail: Photo by Joshua Fuller (Unsplash)

풀이

'훔친 보석의 무게의 곱이 \(K\)와 딱 같게끔 하는 최대 보석의 개수를 구하라' 라는 문제는 결국 \(K\)를 소인수분해 해서 출력하라는 것과 같습니다.

전체 코드

from math import ceil, sqrt
input = open(0).readline
K = int(input())

primes = []
i = 2
while K > 1 and i <= ceil(sqrt(K)):
    if K % i == 0:
        primes.append(i)
        K //= i
    else:
        i += 1

if K > 1:
    print(len(primes) + 1)
    print(*primes, K)
else:
    print(len(primes))
    print(" ".join(map(str, primes)))

solution.py