![]()
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 IOExcep..
![]()
# 구간 합 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합 시간 복잡도 반복문을 통해 i ~ j 인덱스 값들의 합을 구하는 경우) O(N) (i=0, j=N) 시간 복잡도를 줄이기 위해서는 합 배열을 이용해야 함 => O(1)으로 감소 # 합 배열 합 배열 S, 배열 A S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] 합 배열 : 기존의 배열을 전처리한 배열합 배열 만드는 공식 S[i] = S[i-1] + A[i] 합 배열을 이용해 구간 합 구하는 공식 S[j] - S[i-1] # 관련 문제 [JAVA] 백준 q11659 - 구간 합 구하기 4 11659번: 구간 합 ..
