📋 문제 정보

문제 요약

길이가 K인 구간의 합 중 가장 큰 값을 출력

🤔 아이디어

핵심 알고리즘

nums가 [2, 3, 5]일 때 문제의 출력값을 구하기 위해선 다음과 같이 계산한다.

  • g(2) = f(1) + f(2)
  • g(3) = f(1) + f(2) + f(3)
  • g(5) = f(1) + f(2) + f(3) + f(4) + f(5)

볼드로 강조된 부분들이 중복으로 계산되는데 이를 누적합으로 줄일 수 있다.

\[g(n) = g(n - 1) + f(n)\]

의사 코드

divided_sums[num]: num의 약수들의 합

for num in [0, ..., 1_000_000]:
	divided_sums에 100만이하의 num의 배수를 더한다.
	누적합 갱신

return [divided_sums[num] for num in nums]

시간 복잡도

  • 100만 이하의 num의 배수 덧셈: $O(logn)$
\[n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n} = n(1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n})\] \[1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n} = O(logn)\]
  • 누적합 갱신: $O(1)$

최종 시간 복잡도: $O(nlogn)$

🖨️ 입출력 분석

시간 복잡도 분석

  • n이 최대 100만이므로 효율적으로 약수를 구하는 알고리즘을 사용하더라도 $O(\sqrt{n})$이므로 $O(T*\sqrt{n})$은 100,000,000으로 시간 초과가 발생한다. 따라서 모든 수에 대하여 일일히 약수를 구하는 방법은 안된다.

💭 생각 정리

python3으로 제출하면 시간 초과

pypy3으로 제출해야 시간초과가 발생하지 않는다.

📄 소스 코드

import sys

input = sys.stdin.readline
t = int(input())
nums = [int(input()) for _ in range(t)]

def solution(nums):
    divided_sums = [0 for _ in range(1_000_001)]

    for num in range(1, 1_000_001):
        for times in range(num, 1_000_001, num):
            divided_sums[times] += num

        divided_sums[num] += divided_sums[num - 1]

    return [divided_sums[num] for num in nums]

print("\n".join(map(str, solution(nums))))