누적합
BOJ 11659 구간 합 구하기 4 [Java]
BOJ 11659 구간 합 구하기 4 1. 문제 링크 https://www.acmicpc.net/problem/11659 2. 문제 해설 가장 쉽게 생각할 수 있는 방법은 그냥 더해주는 것이다. 근데 이 방법은 시간복잡도가 O(nxm)으로 굉장히 느리기 때문에 다른 방식을 생각해보자. 다른 방법으로는 구간합을 이용한 방법을 떠올릴 수 있다. 특정 구간까지의 합을 저장해둔 배열을 이용하는 방식이다. sum[i]는 처음부터 i개의 원소를 합한 값이다. 즉, 0 ~ i-1 인덱스의 원소의 합을 뜻한다. 그러므로, sum[0]=0 이고, 수들을 입력 받으면서 나머지 sum 배열의 원소들도 채워준다. 구하고자 하는 값이 i번째 수부터 j번째 수의 합이라면 sum[j]-sum[i-1]의 값을 구해주면 O(1)으로 ..