프로젝트 오일러 23번

import math
arr=[]
arr_result=[]
sum_result=0
def isChogwasoo(n):
    sum=1
    for i in range(2,(int)(math.sqrt(n))+1):
        if(n%i==0):
            temp=(int)(n/i)
            if(temp!=i):
                sum=sum+i
                sum=sum+temp
            else:
                sum=sum+temp
    if(sum>n):
        return True
    else:
        return False
for i in range(1,28124):
    if(isChogwasoo(i)):
        arr.append(i)
for i in range(0,len(arr)):
    for j in range(0,len(arr)):
        arr_result.append(arr[i]+arr[j])
arr_result=list(set(arr_result))
for i in range(1,28124):
    sum_result=sum_result+i
for i in range(0,len(arr_result)):
    if(arr_result[i]>28123):
        break
    sum_result=sum_result-arr_result[i]
print(sum_result)
#반환 시간 : 16.7s

오랫동안 헤멘 2페이지의 두 번째 문제이다.

일단 초과수를 구해야 하는데

초과수 판정이 너무 오래 걸려서 약수를 구하는 방법을 생각해 보았고,

어떤 수의 약수를 쭉 나열해보았을 때, 대칭되는 숫자들의 곱이 어떤 수가 된다는 것을 보고

약수를 구하는 알고리즘을 새로 짜 봤더니

시간 면에서 많이 개선되어 이번엔 정답을 볼 수 있겠구나 하는 생각을 했다.

사실 항상 막히던 부분은 지금부턴데,

초과수 '두 개의 합'을 구해야 한다는 부분이다.

생각해보니 '28123을 넘는 모든 정수는 두 초과수의 합으로 나타낼 수 있음이 알려져 있다'는 부분은

최소한 28123 언저리에 있는 초과수를 구했을 때 그 수와 가장 작은 초과수인 12의 합이 28123을 넘어갈 수 있다는 말이므로

그동안 항상 28124의 반인 14062까지의 초과수들의 합을 구해서 계산했던 것과는 달리

28123까지 초과수를 구해서 두 초과수의 합을 구하고 새로운 리스트에 넣어 중복 제거를 해주었다.

그런 다음 1부터 28123까지의 합을 구한 후 

리스트의 요소 값이 28123을 넘어가기 전까지 

리스트 각 요소들만큼 빼 주었더니 답이 나왔다.

오랜 기간 문제를 풀지 못해 글을 쓰지 못했는데

드디어 한 글 더 써서 기분이 좋다.

하지만 3페이지를 풀어야 할 즈음에는 글을 아예 못 쓰게 될 것 같다.