11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
의식의 흐름
구간 합이 뭔지 제대로 공부 안하고 무작정 풀어보기 -> (시간제한 안보고) 그냥 인덱스로 for문 돌리면 되는데 왜 실버지? -> 시간초과ㅎ...
풀이
1. 부분 합 배열 만들기
2. 인덱스 받아서 부분 합 적절하게 사용하기
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 수의 개수
int M = Integer.parseInt(st.nextToken()); // 합을 구해야 하는 횟수
int[] sums = new int[N+1]; // 합 배열
int sum = 0;
st = new StringTokenizer(br.readLine());
for(int i=1;i<=N;i++){
sum += Integer.parseInt(st.nextToken());
sums[i] = sum;
}
while(M>0){
st = new StringTokenizer(br.readLine());
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());
bw.write(Integer.toString(sums[j]-sums[i-1])+"\n");
M--;
}
bw.flush();
br.close();
bw.close();
}
}
알고리즘 정리
[알고리즘] 구간 합 (Prefix Sum)
# 구간 합 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합 시간 복잡도 반복문을 통해 i ~ j 인덱스 값들의 합을 구하
monicajo074.tistory.com
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q11003 - 최솟값 찾기 (0) | 2023.08.08 |
---|---|
[JAVA] 백준 q17276 - 배열 돌리기 (0) | 2023.06.22 |
[JAVA] 백준 q1253 - 좋다 (1) | 2023.06.10 |
[JAVA] 백준 q1072 - 게임 (0) | 2023.05.01 |
[JAVA] 백준 q16953 - A → B (0) | 2023.05.01 |