![[11441번] 합 구하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F8QJdx%2FbtqwLBWgX6L%2FO7ru0HLisQPFKqpBVpHFc1%2Fimg.png)
반응형
11441번: 합 구하기
첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 각 구간을 나타내는 i와 j가 주어진다. (1 ≤ i ≤ j ≤ N)
www.acmicpc.net
$N ( 1 \leq N \leq 10,000 ) $개의 숫자를 입력받고, 구간을 $ M ( 1 \leq M \leq 10,000 ) $만큼 입력하면 그 사이의 수를 더한 값들을 각각 출력해주는 문제입니다.
처음에 그냥 구간만큼 for문을 사용하여 반복하면 되지 않을까를 생각했지만, 그래서는 시간제한 1초를 넘을 것 같았습니다.
계산해보면 $ 10^5 \times 10^5 = 10^{10} $로 족히 10초는 걸릴 수 있는 가능성이 있기 때문입니다.
그래서 저는 제가 Counting Sort를 배웠을 때 알았던 누적 합을 사용하기로 했습니다. 이렇게 하면 시간복잡도가 $O(1)$로 떨어지기 때문입니다.
반응형