백준 17425번 약수의 합

1. 문제 설명

문제링크

두 자연수 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)을 구해보자.

• 입력
  • 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
  • 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
  • 입력의 마지막 줄에는 0이 하나 주어진다.
• 출력
  • 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

2. 코드

import sys

input = sys.stdin.readline

# 자연수의 범위
p = 10 ** 6

# 약수들의 합을 위한 리스트
measure = [1] * (p + 1)

# 문제에서 요구하는 g(x)를 위한 리스트
hap = [0] * (p + 1)

# 모든 약수들의 합을 메모제이션 즉, 리스트 값을 미리 계산해서 저장해두기 위함이다.
# 매번 값을 구하기 위해 반복문을 돌리는 것보다 미리 돌려놓고 그 값을 갖고 오는게 시간효율상 빠르기 때문이다.
for i in range(2, p + 1):
    for j in range(i, p + 1, i):
        # j값은 i로 나누어 지는 값이기 때문에 measure[j]에 i값을 더해준다.
        measure[j] += i
# 정답을 위한 리스트
answer = []

# g(x)를 구하는 과정
for i in range(1, p + 1):
    # hap[i]는 i - 1 있던 값과 f(i) 값을 지속적으로 더 한 값이다.
    hap[i] = hap[i - 1] + measure[i]

# 반복문 안에 int(input())을 받아서 반복문 진행
for _ in range(int(input())):
    # n값 입력
    n = int(input())
    # 해당 되는 g(n) 값을 answer에 넣어준다 (넣어주고 보여주는게 더 빠를 거라고 생각이 들었다.)
    answer.append(hap[n])
# 정답출력
for i in answer:
    print(i)

3. 회고

Q. 문제를 보고 든 생각

• 골드 4문제 답게 문제부터 이해가 잘 되지 않았다. 하지만 게속 읽다보니 어떠한 약수의 합을 지속적으로 요구 한다는 느낌을 받았다.
• 그럼 입력을 받을때 마다 계산을 하게 되면 시간적으로 비효율적이라고 생각이 들었기 때문에 메모제이션 개념을 떠올려서 이를 이용했습니다.

4. 아쉬운 점 혹은 고쳐야 할점

조금더 좋은 풀이가 있다면 댓글로 알려주세요