[Baekjoon 27065] 2022년이 아름다웠던 이유 | Python

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

---

문제

 

어떤 수가 있을 때 그 수의 자기 자신을 제외한 약수들의 합이 그 수보다 크면 과잉수, 같으면 완전수, 작으면 부족수라고 한다.

어떤 양의 정수 $ n $ 이 주어질 때 $ n $ 이 과잉수이면서 $ n $ 의 모든 약수가 과잉수가 아닌지 구하는 문제이다.

 

---

풀이

 

먼저 약수를 구하는 알고리즘을 사용해야 한다. 이 문제에서는 양의 정수만 고려하기 때문에 양수인 경우만 생각한다.

양수인 경우 자기 자신보다 작으면서 자기 자신을 나누었을 때 나머지가 0 인 수를 찾으면 약수이다.

이 문제의 경우 주어지는 양의 정수 $ n $ 이 5000 보다 작으므로 쉽게 나머지가 0 인 수를 찾겠다.

약수를 구하여 리스트로 반환하는 함수를 구현했다면, 이 함수를 이용해서 약수의 리스트를 반환받을 수 있고, 이 리스트의 합을 구하여 양의 정수 $ n $ 이 과잉수인지 판별할 수 있다. 만약 과잉수가 아니라면 BOJ 2022를 출력하면 된다.

과잉수가 맞다면 각 약수들에 대해서도 같은 방법을 사용해서 과잉수가 아닌지 확인하고, 약수 중 하나라도 과잉수가 있다면 BOJ 2022를 출력하면 된다.

양의 정수 $ n $ 이 과잉수이면서, $ n $ 의 모든 약수가 과잉수가 아니라면 Good Bye를 출력하면 된다.

 

---

코드

 

def get_divisors(n):
    divisors = []
    for i in range(1, n):
        if n % i == 0:
            divisors.append(i)
    return divisors

test = int(input())
for _ in range(test):
    num = int(input())
    divisors = get_divisors(num)
    if sum(divisors) <= num:
        print('BOJ 2022')
    else:
        flag = True
        for i in divisors:
            if sum(get_divisors(i)) > i:
                flag = False
                break
        if flag:
            print('Good Bye')
        else:
            print('BOJ 2022')