[Python] 백준 17427번 : 약수의 합 2

💡문제

백준 17427번 문제 링크

🍀풀이

수학 문제만 나오면 자신이 없어진다....약수지만...

일단 문제를 보고 자연수 N보다 작거나 같은 f(Y)값들을 구해서 더하면 되겠구나! 해서 약수를 구하는 식으로 코드를 작성했더니 시간초과가 났다... 그래 그럴 줄 알았다.

시간 초과 코드

n = int(input())

result = 0

for i in range(1, n + 1):
    for j in range(1, int(i**(1/2)) + 1):
        if i % j == 0:
            result += j
            if j != i // j:
                result += i // j
print(result)

시간 복잡도를 계산해보니 이렇게 풀면 시간 복잡도가 O(n√(n))이 나오게 된다.

이 문제의 경우, N=1,000,000이므로 O(nlogn)보다 시간이 덜 걸려야한다.

N=6이면
f(1) = 1
f(2) = 1 2
f(3) = 1 3
f(4) = 1 2 4
f(5) = 1 5
f(6) = 1 2 3 6

여기서 볼 수 있는건 각 i의 배수들은 모두 i를 약수로 가지는 것을 알 수 있다.

맞은 코드

n = int(input())

result = 0

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

print(result)

이렇게 작성하면 O(N)시간으로 코드를 구현할 수 있다.

시간복잡도를 잘 생각하면서 짜야겠다...