백준 17427번 파이썬 문제풀이(수학 - 약수의 합2)

 

코드 

n = int(input())

sum_ = 0
for i in range(1, n + 1):
    # 1부터 n 범위내에서 i의 배수의 개수 = 1부터 n의 범위내에서 i를 약수로 가지는 개수(n을 i로 나눈 몫)
    # 예를들면 1부터 100 까지 11의 배수의 개수는 11,22,33...99 까지 9개 = (100 // 11)
    sum_ += (n // i) * i

print(sum_)

-> 이 문제는 시간제한이 0.5초 밖에 되지 않기 때문에 우리가 아는 기존의 약수를 구하는 식으로는 풀지 못한다. 따라서 다른 조건을 생각해내야 하는데 그 조건은 1부터 n까지 범위 내에서 1부터 n까지의 숫자 i 가 n을 나눈 몫의 개수만큼 나온다는 것이다.  

예를 들면 1부터 100까지의 범위 내에서 1부터 100까지의 숫자 i 가 n // i 의 값만큼 나온다는 것이다. 1은 100개 , 2는 50개 , 3은 30개 .... 

 

이 식을 찾는것이 굉장히 어렵다.. 이 식만 찾으면 식 한줄로 문제를 풀 수 있다.

 

다음은 기존의 우리가 아는 약수를 구하는 식이다. 아래는 O(n2) , O(n√(n)) 의 시간복잡도를 가진다.

 

O(n2)

n = int(input())

sum_ = 0
for i in range(1, n + 1):
    for j in range(1, i + 1):
       if i % j == 0:
           sum_ += j

print(sum_)

 

O(n√(n))

n = int(input())

sum_ = 0

for i in range(1, n + 1):
    for j in range(1, int(i ** 0.5) + 1):
        if i % j == 0:
            sum_ += j
            if i // j != j:  # 예를 들어 i가 25일 경우 5가 두번 들어가는 것을 방지
                sum_ += (i // j)
print(sum_)