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

문제 링크:

https://www.acmicpc.net/problem/17427

17427번: 약수의 합 2

 

---

풀이 유형:

수학, 정수론, 그리디

 

★문제풀이 Point★

1. 시간 복잡도 파악

2. 최적의 해를 도출하기 위한 방법 생각

 

풀이 과정:

이 문제는 자연수 N이 주어졌을 때, g(N)을 구하는 문제이다.

필자는 처음에 O(N^2) 방식을 이용해 하나씩 비교하며 답을 구하려고 했다. 그러나 주어진 문제에서 N = 1,000,000이므로 O(N^2)은 시간 초과임이 분명했다. 따라서 O(N)으로 풀어야 하는 힌트를 문제에서 알려줬다.

이 문제를 어떻게 풀지 곰곰이 생각해보다가 다음과 같은 결론에 도달할 수 있었다.

예를 들어...

N=5일 때
1의 배수는 항상 1을 약수로 가진다.
2의 배수는 항상 2를 약수로 가진다.
3의 배수는 항상 3을 약수로 가진다.
4의 배수는 항상 4를 약수로 가진다.
5의 배수는 항상 5를 약수로 가진다.

 

이를 일반화시켜보면 N의 배수는 항상 N의 약수를 가진다.

즉, N이하의 자연수에서 K를 약수로 가지는 개수는 N/K임을 알 수 있다.

결론적으로 g(N) = 1 * N/1 + 2 * N/2 + 3 * N/3... N * N/1 식을 도출하였다.

이제 O(N)으로 코드를 구현할 수 있게 되었다.

for 구문을 1번만 반복해서 g(N)을 구해보자.

 

풀이 코드:

# 17427번 약수의 합 2

# 약수 구하기
n = int(input())
sum = 0

for i in range(1, n+1):
    # i의 배수 개수 = i를 약수로 가지고 있는 수의 개수
    sum += (n//i) * i
# 정답
print(sum)

 

17427 약수의 합 2