Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 모두를 위한 딥러닝
- HTTP
- 팀플회고
- 백준 4949번
- 데베
- 백준 5525번
- 정리
- 백준
- 깃허브 토큰 인증
- 딥러닝
- 백준 4358번
- 리액트 네이티브
- 백준 4358 자바
- 데이터베이스
- 리액트 네이티브 시작하기
- 깃 터미널 연동
- React Native
- 문자열
- 리액트 네이티브 프로젝트 생성
- SQL
- 깃허브 로그인
- 깃 연동
- 네트워크
- 자바
- 스터디
- 모두를위한딥러닝
- 머신러닝
- 모두의네트워크
- 모두의 네트워크
- 지네릭스
Archives
- Today
- Total
솜이의 데브로그
백준 11659번 ) 구간 합 구하기4 (java) 본문
https://www.acmicpc.net/problem/11659
문제
풀이
import java.io.*;
import java.util.StringTokenizer;
public class BOJ_11659 {
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[] num = new int[N+1];
num[0] = 0;
st = new StringTokenizer(br.readLine(), " ");
for(int i=1; i<N+1; i++){
num[i] = num[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());
System.out.println(num[end]-num[start-1]);
}
}
}
처음에 문제만 봤을 때는 단순히 배열에 저장하고, 저장한 배열에서 다 더해서 출력하려고 했다.
그러나 이런 문제는 누적합을 이용하는 문제로, 누적하여 더한 값을 저장 후 그만큼을 빼서 계산해야하는 문제이다.
그렇다면 굳이 입력된 수를 배열로 저장할 필요가 없으므로, 입력 받으면서 바로바로 누적합을 구해서 배열에 저장하고, 출력한다.
이때, num[end] - num[start-1] 이어야 함을 기억하자!
'Algorithm > 백준' 카테고리의 다른 글
백준 1158번 ) 요세푸스 문제 (java) (0) | 2022.03.15 |
---|---|
백준 2178번 ) 미로 탐색 (java) (0) | 2022.03.11 |
백준 1991번 ) 트리 순회 (java) (0) | 2022.03.09 |
백준 1260번 ) DFS와 BFS (java) (0) | 2022.03.09 |
백준 2748번 ) 피보나치 수 2 (java) (0) | 2022.02.24 |