[백준] 11659. 구간 합 구하기 4
문제 링크Permalink
풀이 과정Permalink
N과 M이 최대 100,000 까지 가능하므로, 최악의 경우 10101010 번의 탐색이 이루어지므로, 전부를 순회하는 방식의 풀이는 시간초과가 발생하게 됩니다. 따라서, 저는 왼쪽과 오른쪽 각각을 기준으로 시작되는 구간의 합을 미리 구해놓아 사용했습니다.
위 예제와 같이 입력을 받고 나면, 왼쪽부터 누적된 값을 요소로 갖는 배열 left 와 오른쪽부터 누적된 값을 요소로 갖는 배열 right 를 만들어 줍니다.
예를 들어, 구간 [2, 4] 의 합을 구하려고 한다면, 전체 구간 [1, 5]에서 [1, 2) 구간의 합과 (4, 5] 구간의 합을 빼주면 구할 수 있습니다.
왼쪽 노란색 구간의 총합은 left[1] 에 위치할 것이고, 오른쪽 주황색 구간의 총합은 right[5]에 위치할 것입니다.
따라서, 총 합에서 left[1] 과 right[5] 를 빼주면 구간 [2, 4] 의 합을 구할 수 있습니다.
코드Permalink
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N + 1];
int[] left = new int[N + 1];
int[] right = new int[N + 1];
int total = 0;
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
total += arr[i];
}
int sum = 0;
for (int i = 1; i <= N; i++) {
sum += arr[i];
left[i] = sum;
}
sum = 0;
for (int i = N; i >= 1; i--) {
sum += arr[i];
right[i] = sum;
}
StringBuilder answer = new StringBuilder();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int subsum = total;
if (a - 1 >= 1) subsum -= left[a - 1];
if (b + 1 <= N) subsum -= right[b + 1];
answer.append(subsum + "\n");
}
System.out.println(answer);
}
}
댓글남기기