BOJ 17427 - 약수의 합 2 (Python3)
어렵다고 꼭 고급 테크닉을 사용하는 문제일 리 없고, 고급 테크닉을 사용한다 하더라도 생각보다 쉬운 문제일 수 있다.
특히 고급 테크닉을 사용하는 기본이 되는 문제라면 더욱. 잘못 말리면 끝까지 못 풀 수 있지만 해법을 알게 된다면 생각보다 순식간에 풀 수 있는 문제이다.
그럼 본격적으로 풀이에 돌입해 보자.
문제
두 자연수 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)이 주어진다.
예제 입력)
# 예제 입력 1
1
# 예제 입력 2
2
# 예제 입력 3
10
# 예제 입력 4
70
# 예제 입력 5
10000
출력
첫째 줄에 g(N)를 출력한다.
예제 출력)
# 예제 출력 1
1
# 예제 출력 2
4
# 예제 출력 3
87
# 예제 출력 4
4065
# 예제 출력 5
82256014
내 코드
ans,N = 0,int(input())
for i in range(1,N+1):
ans += i*(N//i)
print(ans)
f(n)을 n의 약수의 합으로 분해해서 보자. f(6)같은 경우 12로 보는 대신 1+2+3+6으로 보자는 이야기다. 그렇다면 g(N)을 모두 합으로 표기했을 때, d라는 수는 몇 번 나올까?
f(n)에서 d가 나오려면, d가 n의 약수여야 한다. 당연한 소리라고? 그렇다면 그 반대로 표기하면 어떨까. n이 d의 배수여야 한다는 것이다.
그러한 n은 1부터 N 사이에 몇 개 있을까? 정확하게 \(\lfloor\frac{N}{d}\rfloor\)개 있을 것이다. N을 d로 나눈 몫만큼 말이다.
그러니 총 d의 합은 \(d\lfloor\frac{N}{d}\rfloor\)일 것이다. 이를 1≤d≤N에 대해서 모두 대해주면 끝.
원래는 n에 대해서 f(n)을 더하는 문제였지만, 이제는 d에 대해서 \(d\lfloor\frac{N}{d}\rfloor\)를 세는 것으로 바꾸어 더 쉽게 풀었다.
이러한 기법을 더블 카운팅이라고 한다. 우회적으로 문제를 풀 때 특히 자주 사용하는 방법이고, 백준과 같은 문제풀이 사이트에도 적지 않으니 기억해 두는 것도 나쁘지 않다.
이로서 17427번의 풀이를 마친다.
