백준 #17427 약수의 합 2

일단 문제.. 뭐라 써있지만 내가 이해한 것은 아래와 같다

문제

입력값 이하의 모든 자연수의 약수의 합을 더한 값을 출력

1차 답 (타임 아웃 뜸 ㅠ)

n = int(input())
count = 0

for i in range(1, n+1):
    result = set()
    for j in range(1, i+1):
        if i%j==0:
            result.add(j)
    result = list(result)
    count += sum(result)

print(count)

일단 바로 생각나는 대로 적어봤다.
그리고 오 답 나오네? 하고 제출하자마자 시간 초과로 빠꾸먹었다
그래서 뭐가 문제냐며 한참을 눈으로 화면에 말걸고 있었다.
시간복잡도가 문제라고 해서 일단 아 절대 다중반복은 안되겠거니 생각을 했다.
나는 결국 질문과 힌트를 찾아 구글로 여행을 떠났고 성공적으로 힌트를 얻어 답을 맞출 수 있었다.
다양한 시각으로 문제 해결 방법을 찾는 것이 정말 정말 필요하다고 느꼈다..

지국민이 시야가 좁은 것이 단점이라고 했는데, 국민이를 좋아해서인지 닮아버린 것 같다 큰일이다.

정답

n = int(input())
sum = 0

for i in range(1, n+1):
    sum += (n//i)*i
print(sum)

내가 구글로 여행을 떠나 얻은 귀중한 힌트는 [패턴을 찾아라]였다.
입력값이 10일때부터 한번 쭉 어떻게 계산되는지 적어봤는데, 12 정도까지 생각해보니 특정 패턴이 내 눈에 띄었다.
그래서 얻은 나의 답!

1차 제출 코드에 비해 정말 간결해지고, 수행 시간도 빨라져서 기분 좋았다.
근데 정답자 보니까 시간을 더 줄인 사람들도 많았어서 나중에 시간이 된다면,
시간을 어떻게 줄일 수 있을지 생각을 해 보면 좋겠다 싶었다.
이래놓고 안한 게 너무 많아서 꼭.. 하려고 노력해야지.