[BOJ]17427 - 약수의 합 2 (Python)

문제

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

코드 #1 - WRONG❌

#약수의 합 구하는 함수
def f(x):
    global list
    sum=0
    for i in range(1, x+1):
        if(x%i==0):
            list.append(i)

    for z in list:
        sum += z

    list = []
    return sum

list = []
totalSum =0
n = int(input())
for j in range(1, n+1):
    totalSum += f(j)

print(totalSum)

풀이 #1 - WRONG❌

처음에는 모든 약수를 구하고, 그 약수의 합을 또 구하는 방법으로 풀었었다.

예제5에서 시간이 조금 걸리기는 했지만 pypy로 하면 될거라고 생각하고 제출했는데 시간초과가 났다.

다른 방법을 떠올릴 수 없어서 다른 블로그를 참고하여 다시 풀었다.

코드 #2

n = int(input())
sum=0

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

print(sum)

풀이 #2

블로그를 찾아보니 문제에서 패턴을 찾으라고 하였다.

N=10일 때 모든 약수들을 나열해보았다.

이 때 약수들의 합에서 패턴을 찾을 수 있었다.

1은 총 10번 더해지고, 2는 총 5번 더해진다.

3은 3번, 4는 4번 ... 6, 7, 8, 9, 10은 1번씩 더해졌다.

각 약수로 10을 나눈 몫이 이 약수들의 개수가 되는 것이다.

각 원소의 합 = (N//i) \* i

 

문제를 풀 때 이런 아이디어를 생각해 낼 수 있는 힘도 필요한 것 같다. 

많이 풀면 자연스럽게 센스가 생기지 않을까..?하는 기대를 해본다.