BOJ 6975 - Deficient, Perfect, and Abundant

문제

BOJ 6975 - Deficient, Perfect, and Abundant

자연수 n이 주어질 때, n의 자기 자신을 제외한 양의 약수의 합을 구한다. 약수 합이 n보다 작으면 "deficient", 같으면 "perfect", 크면 "abundant" 숫자임을 판별하여 출력한다.

입력

• 첫 줄: 테스트 케이스 수 T
• 각 케이스: 자연수 n (1 ≤ n ≤ 100)

출력

각 케이스마다 n is a deficient/perfect/abundant number. 형식으로 출력하고 빈 줄을 삽입한다.

예제

풀이

n의 약수를 브루트포스로 모두 구한 뒤 합산하고, n과 비교하여 세 가지 유형 중 하나로 분류한다.

1. 1부터 n-1까지 순회하며 n을 나누는 수를 약수로 수집한다.
2. 수집된 약수의 합을 n과 비교한다.
3. 합이 n보다 작으면 "deficient", 같으면 "perfect", 크면 "abundant"를 출력한다.
4. 각 결과 뒤에 빈 줄을 출력한다.

핵심 아이디어: 리스트 컴프리헨션 [i for i in range(1, n) if n % i == 0]으로 약수를 한 줄에 수집하고, sum()으로 합산한다. n이 최대 100으로 작으므로 O(N) 브루트포스가 충분히 효율적이다.

코드

import sys
 
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    lst = [i for i in range(1, n) if n % i == 0]
    if sum(lst) < n:
        print(n, "is a deficient number.")
    elif sum(lst) == n:
        print(n, "is a perfect number.")
    else:
        print(n, "is an abundant number.")
    print()

복잡도

• 시간: O(N²)
• 공간: O(N)