[백준] 17390 이건 꼭 풀어야 해!

문제

• N짜리 수열 A를 비내림차순으로 정렬한 수열 B를 만들었다.
• 이때 수열 B에 대한 질문 Q개가 주어진다.
  • 질문 : B_L ~ B_R 까지의 합 구하기 
  • 1 <= N, Q <= 300,000
  • 1 <= Ai <= 1,000

 

풀이

• 누적합 구하기 (문제 조건 : 비내림차순으로 정렬한 후!)
• 시간 복잡도
  • 그냥 다 더하는 방식으로 한다면, O(N^2)으로 시간초과

 

import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
sum_nums = [0]
for i in range(N):
    sum_nums.append(sum_nums[-1] + nums[i])

for _ in range(Q):
    l, r = map(int, input().split())
    print(sum_nums[r] - sum_nums[l-1])

 

References

• 백준 17390번
• 2023/04/21 오늘의 문제