[백준/파이썬] 17427번: 약수의 합 2 풀이

🔗 문제 링크

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

17427번: 약수의 합 2

  문제 이름 그대로 약수의 합을 구하는 문제이지만! 수학적인 계산을 사용해야 제대로 풀 수 있는 문제이다.

 

---

🔎 문제 풀이 & 작성 코드

  문제에서 자연수 A가 있을 때, 이 자연수의 모든 약수를 더한 값을 f(A)로 표현하였다. 또한, x라는 자연수가 주어졌을 때 x보다 작거나 같은 모든 자연수 y(1~x까지)의 f(y)값을 모두 더한 값을 g(x)로 표현하였다. 이때, 주어진 자연수 N에 대한 g(N)을 구하면 된다. 

 

틀린 풀이

  처음에는 문제의 조건에 맞게 직접적으로 구현했다. 1~x까지, 각각의 f(y)를 구하고 이를 모두 더해주었다. 가장 직관적인 방법이지만, N의 범위가 1~1,000,000까지 이므로 숫자가 커질수록 for문의 반복이 많기 때문에 시간초과가 발생하였다. 그래서 다른 풀이를 찾아보았다.

import sys
N = int(sys.stdin.readline())

answer = 0

for x in range(1,N+1):
    answer+=sum([y for y in range(1,x+1) if x%y == 0])
print(answer)

 

정답 풀이

  문제에 주어진 조건에 '두 자연수 A와 B가 있을 때, A = B*C를 만족하는 자연수 C를 A의 약수라고 한다.'라는엄청난 힌트가 숨겨져 있었다. k의 배수는 항상 k을 약수로 갖는다. 따라서 1부터 N까지의 모든 숫자를 임의의 숫자 k로 나누었을 때 나누어 떨어진다면 그 수는 k를 약수로 가진다. 그렇기 때문에 N이하의 모든 자연수에서 K를 약수로 가지는 숫자의 개수는 N/K(나눈 몫. 나머지는 버림)이다. 숫자를 대입해 보면 훨씬 이해가 잘된다. 말로 하는 설명보다 예시가 이해하기 더 쉬워서 예시를 하나 들어보겠다.

 

N = 6일 때, 각 경우의 수를 살펴보자.

k = 1일 때, N/k = 6 ⇒ 1~6까지의 자연수 중에서 1을 약수로 갖는 수는 6개이다. (1,2,3,4,5,6)

k = 2일 때, N/k = 3 ⇒ 1~6까지의 자연수 중에서 2를 약수로 갖는 수는 3개이다. (2,4,6)

k = 3일 때, N/k = 2 ⇒ 1~6까지의 자연수 중에서 3을 약수로 갖는 수는 2개이다. (3,6)

k = 4일 때, N/k = 1 ⇒ 1~6까지의 자연수 중에서 4를 약수로 갖는 수는 1개이다. (4)

k = 5일 때, N/k = 1 ⇒ 1~6까지의 자연수 중에서 5를 약수로 갖는 수는 1개이다. (5)

k = 6일 때, N/k = 1 ⇒ 1~6까지의 자연수 중에서 6을 약수로 갖는 수는 1개이다. (6)

 

  문제에서는 약수의 합을 구하라고 했으니, 1~6까지의 k*(N//k)를 모두 더하면 된다. 이를 일반화하여 코드에 적용하면 아래와 같다.

import sys
N = int(sys.stdin.readline())

answer = 0

for x in range(1, N+1):
    answer+=(N//x)*x
print(answer)

  수학적인 원리를 이용해 푸는 문제들을 풀 때마다 어떻게 이런 생각을 해내는지 경이로울 뿐이다.. 자연과학의 이런 부분이 정말 멋있는 것 같다.

 

 

---

🌍 깃허브 링크

실제 작성한 해당 정답 코드는 깃허브에도 업로드해두었습니다.

dohyun-99 - Overview