구간 합 구하기1 / 백준 11659
2024. 6. 19. 00:51ㆍ카테고리 없음
문제
https://www.acmicpc.net/problem/11659
풀이
알고리즘을 풀기 전에 데이터의 범위가 얼마나 큰지 확인하는것이 좋습니다. 항상 최악의 케이스를 감안하고 알고리즘을 짜야 하기 때문에 N과 M의 최대수를 대입해도 시간안에 통과가 되는지를 체크 하는것이 좋습니다.
N의 최대수 100000 숫자의 구간합을 M의 최대수 100000만회 구하게 되면 100000 곱하기 100000으로 연산횟수를 1억번을 넘게 되어 제한시간 1초안에 푸는게 풀가능 합니다. 그렇기 때문에 N 숫자만큼 반복하는 동안 합 배열을 생성하여 합배열을 통한 구간합을 출력 하는 방식으로 로직을 구현하면 됩니다.

합배열이 S[ ]일때 구간합 구하는 공식
배열 A의 i ~ j까지 구간합을 구하는 공식 = S[ j ] - S[ i -1 ]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class 구간합구하기_11659 {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int M = Integer.parseInt(s[1]);
String[] numbers = br.readLine().split(" ");
int[] addNum = new int[N];
// 합 배열 addNum 구하기
for (int i=0 ; i<N ; i++) {
if (i==0) addNum[0] = Integer.parseInt(numbers[0]);
else addNum[i] = addNum[i-1] + Integer.parseInt(numbers[i]);
}
int cnt = 0;
StringBuffer sb = new StringBuffer();
while (cnt < M) {
String[] s1 = br.readLine().split(" ");
int i = Integer.parseInt(s1[0]) - 1; // 인덱스는 0부터 시작하므로 인덱스에 맞추기 위해 -1
int j = Integer.parseInt(s1[1]) - 1;
if (i == 0) sb.append( addNum[j] + "\n");
else sb.append((addNum[j] - addNum[i - 1])+"\n");
cnt++;
}
bw.write(sb.toString());
bw.flush();
bw.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}