[solved.ac 실버2] 17427_약수의 합 2 (python, math)

제약 사항

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y) 값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

 

---

나의 풀이

풀이 시도

여러 번의 시간 초과 끝에 맞춘 문제이다. 그만큼 이 문제를 풀 수 있는 방법도 다양하고, 훨씬 더 효율적인 풀이가 존재한다는 의미이다.

실패한 코드들은 깃허브에 올려놓았다.

 

 

예시: 19가 입력된 상황

모든 수는 1과 자기 자신으로 나누어 진다.

모든 경우에서 1과 자기 자신이 더해져야 한다. 이때, 1은 1 자체이기 때문에 두 번 더해지지 않도록 주의해야 한다.

1 이후의 수 i는 i^2부터 확인한다.

i가 2일 때 2의 제곱인 4부터 확인해야 한다. 왜냐하면 2는 이미 1과 짝지어졌기 때문이다. 이때도 주의해야 할 것은 2가 두 번 더해지지 않도록 주의해야 한다는 것이다.

i가 3일 때도 동일한 과정으로 추가된다.

i가 4일 때는 제곱 수인 16부터 시작하지만, 더 이상 추가되지 않는다. 현재 19가 입력된 상황을 보는 것이기 때문이다.

이후 5, 6, 7,... 모두 추가될 수 없다. 제곱 수가 19보다 크기 때문이다.

즉, 입력된 수가 n이라면 n의 제곱근까지만 확인하면 된다.

위 표에서 1~19 밑에 적혀있는 숫자들을 모두 더하면 구하고자 하는 답이 된다.

 

더하는 방법

우선, 위 표를 기준으로 행의 1, 2, 3, 4 숫자는 i로, 열의 1, 2, 3,..., 19 숫자는 n으로 부르겠다.

 

i가 1인 경우 1과 자기 자신을 합하면 된다. (단, n이 1일 때는 예외적인 경우이므로 따로 더해준다)

2는 1+2, 3은 1+3, 4는 1+4... 19는 1+19이다. 즉, 3~20까지의 합을 구하고 1을 따로 더해주면 된다.

 

i가 2인 경우 2 + (2+3) + (2+4) + (2+5) + (2+6) + (2+7) + (2+8) + (2+9)이다.

정리하면 2 * 7 + (2~9까지의 합)으로 나타낼 수 있다.

 

i가 3인 경우 3 + (3+4) + (3+5) + (3+6)이다.

정리하면 3 * 3 + (3~6까지의 합)으로 나타낼 수 있다.

 

i가 4인 경우 4이다.

 

i가 1보다 큰 경우엔 다음과 같이 일반화시킬 수 있다.

i * ((n-i*i) // i) + sum(i ~ n//i)

 

이것을 코드로 나타내면 다음과 같다.

sum_range = lambda s, e: e*(e+1)//2 - s*(s-1)//2

def solution():
    n = int(input())
    answer = 1
    
    answer += sum_range(3, n+1)
    
    for i in range(2, int(n**0.5)+1):
        answer += i * ((n-i*i) // i) + sum_range(i, n//i)
    
    print(answer)
    
solution()

sum_range는 s부터 e까지 연속된 숫자의 합을 구하는 함수이다.

 

채점 결과