17427

날짜 : 2022. 12. 13

사용 언어 : python

 

문제

 

 

코드

시간초과(시간복잡도 : O(n√n)

import sys

n = int(sys.stdin.readline())
g = 1


def f(num):
    t = 0
    for i in range(1, int(num ** 0.5)+1):
        if num % i == 0:
            if i == (num // i): t += i  # 제곱
            else: t += (i + num // i)
    return t


for i in range(2, n+1):
    #print(i, f(i))
    g += f(i)
print(g)

 

정답

import sys

n = int(sys.stdin.readline())
g = 0

for i in range(n, 0, -1):
    g += i * (n // i)
print(g)

 

 

풀이

- 예를들어 n = 5라고 가정하면 1부터 5까지의 함수 f값은 다음과 같다.

f(1) = (1) -> 1

f(2) = (1, 2) -> 2

f(3) = (1,3) -> 3

f(4) = (1, 4) (2) -> 1 + 4 + 2 = 7

f(5) = (1, 5) -> 6

 

- 여기서 각각의 약수들을 살펴보면 1은 5번 등장, 2는 2번 등장, 3, 4, 5는 각각 1번씩 등장하는 것을 알 수 있다.

- 즉, 배수의 관점으로 접근한다면 1의 배수는 1부터 5가 될 것이고, 2의 배수는 2, 4가 되며, 3은 3, 4는 4, 5는 5가 된다.

- 그러므로 g(n) = 1 * (n // 1) + 2 * (n // 2) + 3 * (n // 3) + ... n * (n // n) 이라는 공식이 도출된다.

- 약수의 관점이 아닌 배수의 관점으로 접근했을 때 해결할 수 있었던 문제였다.

 

 

 

알게된 점

- 처음 O(n√n)의 풀이로 접근했지만 제한시간때문에 시간초과가 발생했다.

- 그래서 생각하다가 결국 풀이를 보고 문제를 해결했다.

 

 

참고 사이트

- https://data-flower.tistory.com/95

[백준 17427번] 약수의 합 2 - 파이썬