[BOJ]1659区間求和4
11025 ワード
🔗 Problem
https://www.acmicpc.net/problem/11659
👩💻 Code package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 구간 합 구하기 4
public class BJ11659 {
static int n;
static int m;
static int[] total;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
total = new int[n+1];
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) {
if(i == 1) total[i] = Integer.parseInt(st.nextToken());
else total[i] = total[i-1] + Integer.parseInt(st.nextToken());
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
long sum = total[end] - total[start-1];
sb.append(sum).append("\n");
}
System.out.println(sb.toString());
}
}
💡 Learned 아이디어
package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
// 구간 합 구하기 4
public class BJ11659 {
static int n;
static int m;
static int[] total;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
total = new int[n+1];
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++) {
if(i == 1) total[i] = Integer.parseInt(st.nextToken());
else total[i] = total[i-1] + Integer.parseInt(st.nextToken());
}
for(int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
long sum = total[end] - total[start-1];
sb.append(sum).append("\n");
}
System.out.println(sb.toString());
}
}
💡 Learned 아이디어
Prefix Sum
アルゴリズムと呼ぶ.Reference
この問題について([BOJ]1659区間求和4), 我々は、より多くの情報をここで見つけました https://velog.io/@ssoyeong/BOJ-11659-구간-합-구하기-4テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol