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

https://www.acmicpc.net/problem/17390

17390번: 이건 꼭 풀어야 해!

 

문제

숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!

욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!! (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)

• L R: BL + BL+1 + ... + BR-1 + BR 을 출력한다.

Figure 1. 모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정

욱제의 질문에 답하고 함께 엠티를 떠나자!!

 

입력

첫 번째 줄에 수열 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개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

 

 

풀이

 

import sys

N, T = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort()
for i in range(T):
    L, R = map(int, sys.stdin.readline().split())
    print(sum(numbers[L-1:R]))

단순히 값을 입력받아서 정렬한 뒤 L ~ R까지 합을 구했다.

시간 초과가 나왔다. 각 명령마다 SUM을 수행하는 것이 문제인 것 같다.
Prefix sum이라는 개념을 이용하여 구간 합을 구해서 풀어야하는 문제라고 생각했다.

 

import sys

N, T = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort()
pre_sum = []
for i in range(N):
    pre_sum.append(sum(numbers[:i+1]))
for i in range(T):
    L, R = map(int, sys.stdin.readline().split())
    if L == 1:
        print(pre_sum[R-1])
    else:
        print(pre_sum[R-1] - pre_sum[L-2])

Pre_sum을 미리 연산해서 각 쿼리에 대해서는 pre_sum을 이용해서 연산하였다.

여전히 시간 초과가 발생했다.
pre_sum을 구할때도 sum을 사용하지 않고 해야하는 것 같다.

 

 

전체 코드

import sys

N, T = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort()
pre_sum = [numbers[0]]
for i in range(1, N):
    pre_sum.append(pre_sum[i-1]+numbers[i])
for i in range(T):
    L, R = map(int, sys.stdin.readline().split())
    if L == 1:
        print(pre_sum[R-1])
    else:
        print(pre_sum[R-1] - pre_sum[L-2])

pre_sum을 구하는 것도 dp를 이용하여 이전까지의 합 + 현재 값을 이용하여 계산하였다.

 

구간합에 대한 개념을 찾아보면서 풀었는데 문제에 따라서 단순히 SUM이 아니라 구간합을 사용해야할 수 있다는
것을 생각해야겠다.