코딩테스트-알고리즘/백준 BOJ
[백준 BOJ/Silver III] 11659번 : 구간 합 구하기 4
닉네임생각즁
2024. 3. 5. 23:36
https://www.acmicpc.net/problem/11659
처음에는 단순하게 생각했다
합 구해야하는 구간을 for문 범위에 넣고 구하면되는거 아닌가? 하고 풀었는데 시간 초과,,😮😮
- 1 ≤ N ≤ 100,000
- 1 ≤ M ≤ 100,000
N과 M의 범위가 이렇기 때문에 최대를 생각했을때 N*M이 되고 시간초과가 날 수 밖에 없는 조건이었던거다 누적합을 이용해서 구해야하는 문제였다!!!
입력받은 숫자를 배열에 넣을때 앞에 나온 숫자들을 더하고 쌓아주면서 넣어주면 최종 답을 쉽게 구할 수 있게 된다
최종 코드
package BOJ11659;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
st = new StringTokenizer(br.readLine());
int[] num = new int[N+1];
for (int i = 1; i < N+1; i++) {
int n = Integer.parseInt(st.nextToken());
num[i] = num[i-1] + n;
}
// System.out.println(Arrays.toString(num));
for(int i = 0 ; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int answer = num[y] - num[x-1];
System.out.println(answer);
}
}
}