[백준/Python] 9506번 : 약수들의 합

시간 제한	메모리 제한	문제 티어	정답 비율
2 초	128 MB	브론즈 I	54.813%

📜 문제

어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.

예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.

 

📥입력

입력은 테스트 케이스마다 한 줄 간격으로 n이 주어진다. (2 < n < 100,000)

입력의 마지막엔 -1이 주어진다.

 

📤출력

테스트케이스 마다 한줄에 하나씩 출력해야 한다.

n이 완전수라면, n을 n이 아닌 약수들의 합으로 나타내어 출력한다(예제 출력 참고).

이때, 약수들은 오름차순으로 나열해야 한다.

n이 완전수가 아니라면 n is NOT perfect. 를 출력한다.

 

💡풀이

이 문제는 무한반복문과 for 반복문, 약수 구하는 알고리즘을 알고 있다면 풀 수 있었던 문제였다.

 

-1을 입력받으면 break문을 통해 무한반복문을 탈출하여 프로그램을 종료시키고, -1이 아닌 다른 값이 들어왔으면 약수의 성질(자기 자신을 약수로 나누면 나머지가 0이 되는 것)을 이용하여 조건문을 만들어 해당 약수들을 divisor_list 안에 추가하도록 했다.

 

 

여기서 알아가야 할 점은 바로 for i in range(1, n//2 +1) 이 부분이다. 사실 for i in range(1, n) 해도 결과는 똑같다. 그러나  n의 약수는 자기 자신을 제외하면 n의 절반까지가 모든 약수를 구하므로 n//2 + 1까지만 반복하는게 시간 복잡도도 절반으로 줄이는 효과를 볼 수 있어 빠르게 코드를 돌릴 수 있다는 장점이 있다.

 

내가 작성한 정답코드는 아래와 같다.

import sys

input = sys.stdin.readline

while True:
  n = int(input())
  if n == -1:
    break
  else:
    total = 0
    divisor_list = []
    for i in range(1, n//2 + 1):
      if n % i == 0:
        total += i
        divisor_list.append(i)
    if n == sum(divisor_list):
      print(n, '=', end=' ')
      print(*divisor_list, sep=' + ')
    else:
      print(n, 'is NOT perfect.')