[백준 17390번] 파이썬 - 이건 꼭 풀어야 해!

백준 17390 - 이건 꼭 풀어야 해!

시간 제한 1초, 메모리 제한 512MB

# 조건

• 숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!
• 욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!!
  • L R: BL + BL+1 + ... + BR-1 + BR 을 출력한다.

입력

• 첫 번째 줄에 수열 A의 길이 N과 질문의 개수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)
• 두 번째 줄에 N개의 정수 A1, A2, ..., AN 이 공백으로 구분되어 주어진다.
  • Ai 는 수열 A의 i 번째 수이다. (1 ≤ Ai ≤ 1,000)
• 세 번째 줄부터 Q개의 줄에 걸쳐 욱제의 질문을 의미하는 두 수 L, R이 공백으로 구분되어 주어진다. (1 ≤ L ≤ R ≤ N)
• 주어지는 모든 입력은 자연수이다.

출력

• Q개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

# 접근 방법

• 누적 합과 정렬을 사용하여 풀어준다.
• 비내림차순이므로 입력받은 nums 리스트를 sort()로 정렬해준 후, 누적 합을 구해준다.
• 또한, 1부터 시작하므로 0번 인덱스를 0으로 추가해준 후 해당 구간이 주어지면 end 인덱스의 값 - (start-1)의 인덱스의 값을 해준 뒤 출력한다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

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

for q in range(Q):  
    st, ed = map(int, input().split())  
    print(sums[ed] - sums[st-1])