23327 리그전 오브 레전드

고오급 알고리즘 스터디 - 3

풀이

1번째 시도 : 시간초과 O(QN^2)

• 모든 경우에 대해서 경기의 재미를 구하게 된다면 O(QN^2)으로 시간초과가 발생한다.

2번째 시도 : 시간초과 O(QN)

• 각 팀의 경기 재미를 누적합으로 구한 후 디비전 범위에 속하는 팀들을 돌며 경기의 총 재미를 구한다.
• 이 경우 디비전 범위에 속하는 팀을 도는 O(N)을 디비전의 개수 O(Q) 만큼 시행하여 O(QN)으로 시간초과가 발생한다.
  

3번째 시도 : 메모리 초과

• 1. 중복을 포함한 i번째까지의 팀과 j번째까지의 팀의 경기 재미를 갖는 prefix_sum[i][j] 을 구한다.
  2. 자신과의 경기를 하는 경기 재미의 합을 갖는 prefix_pow를 구한다.
  3. prefix_sum 을 통해 [l, r]에 속하는 팀들의 경기 재미를 구한다.
  4. 이후 자신과의 경기로 발생한 재미를 빼고, 중복 처리를 한다.

• prefix_sum 을 구하는 과정에서 부터 O(N^2)으로 시간초과가 발생하며 배열의 범위가 10^10이 넘어가며 메모리 초과또한 발생하게 된다.

• 문제의 메모리 제한이 1024 MB 로 배열의 크기를 크게 선언해도 메모리 초과가 발생하지 않을 것이라 예상하고 진행했었음.

  

최종 풀이

• 1. 3번째 시도에서 i번째까지의 팀과 j번째까지의 팀의 경기 재미를 갖는 누적합의 경우 메모리 초과와 시간 초과의 원인이었음.
  2. 이러한 누적합은 같은 값의 배열을 곱하는 것 이므로 각 팀의 인기의 누적합의 제곱을 통해 O(N)으로 표현가능하다.
  3. prefix_sum 을 통해 중복을 포함한 [l, r]에 포함된 팀들의 경기 재미를 구한 후 prefix_power 를 통해 자신과의 경기 재미를 제거하고, 중복 처리함
  4. prefix_sum 과 prefix_power 모두 시간복잡도 O(N), 공간복잡도 O(N)으로 구현이 가능하다.
  5. 모든 디비전 경우에 관해 원하는 값을 O(1)로 접근이 가능하여 시간복잡도 O(Q)로 해결이 가능하다.
     

import sys

n, q = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

prefix_sum = [0] * (n+1)
for i in range(1, n+1):
    prefix_sum[i] = prefix_sum[i-1] + a[i-1]

prefix_power = [0] * (n+1)
for i in range(1, n+1):
    prefix_power[i] = prefix_power[i-1] + a[i-1] ** 2

for _ in range(q):
    l, r = map(int, sys.stdin.readline().split())

    total = ((prefix_sum[r] - prefix_sum[l-1]) ** 2) - (prefix_power[r] - prefix_power[l-1])
    total = total // 2

    sys.stdout.write(str(total) + '\n')
    

23327 리그전 오브 레전드