• TOC {:toc}

이 글은 백준 온라인 저지의 11653번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.03.25

메모리 시간 코드 길이
28776 KB 1488 ms 169 B 
N = int(input())
if N == 1:
    quit(0)
else:
    i = 2
    # N이 1이 될 때 까지 수행
    while N > 1:
        if N % i == 0:
            print(i)
            N //= i
        else:
            i += 1

아이디어 & 풀이

오름차순으로 소인수분해 하면 소수가 아닌 수들은 그 전에 작은 소수에 의해서 나뉘게되므로 i를 2부터 순차 증가하면서 입력받은 수를 나눈다.

함수가 아니라서 N == 1일 때 return 사용이 불가능했다. 대신 quit을 사용했다.

피드백

  • 입력한 수의 제곱근까지만 체크하는 게 속도에 영향을 가장 많이 미친 것 같다. (내 풀이 1744ms, 다른 풀이 56ms)
  • N이 1인 경우를 먼저 하나의 경우로 다루는 것보다 소인수분해를 한 뒤 소인수분해가 안 되는 N 중에서 1을 제외(출력하지 않음)하는 게 더 깔끔한 것 같다.
  • 제곱근까지 모든 수를 확인하는 것보다 소인수 분해가 끝나는 N == 1인 순간에 반복을 그만두는 게 효율적이라고 생각했는데 N == 1을 확인하는 과정 때문에 오히려 더 오래 걸릴 수도 있을 것 같다.

참고 답안

n = int(input())
i = 2
r = int(n ** 0.5)

# i가 자신의 제곱근이 될 때까지 수행
while i <= r:
    # n이 i로 나누어떨어지면
    while not n % i:
        # i를 출력하고
        print(i)
        # n을 n을 i로 나눈 값으로 변경
        n //= i
    # 더 i로 나뉘지 않으면 i를 증가
    i += 1
# 소인수분해가 되지 않는 수(소수)인 경우
# 1보다 크면 출력 (1은 출력 안 하기 위함)
if n > 1:
    print(n)

아이디어 & 풀이

i를 2부터 증가시키면서 입력받은 수를 나눈다.

약수가 존재할 경우 자신의 제곱근을 기준으로 대칭적으로 존재하기 때문에 i 값을 입력받은 값의 제곱근까지만 증가시켜도 된다.