백준 11659 - 구간 합 구하기4(JAVA)

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

이 문제는 단순하게 i번째 부터 j번째까지의 합을 구하는 문제이다. 하지만 숫자의 개수가 최대 10만개이고 연산의 회수 또한 최대 10만개 이기 때문에, 매 연산마다 합을 구한다면 시간 초과(10만 * 10만)로 풀 수가 없다. 문제의 이름 처럼 구간 합을 미리 구해두면 연산 회수를 N * M 에서 N + M 수준으로 줄일 수가 있다.

 

 

1. i번째까지의 구간의 합은 i번째의 숫자와 i - 1번째까지의 합이 더해진 값이다.

-> sums[i + 1] = nums[i] + sums[i]

2. sums(구간 합)의 배열의 길이를 + 1 이유는 1번 구간부터의 합을 구할 때 계산을 편리하게 하기 위해서이다. 1번째 구간에 대해서 분기 처리하는 것보다 코드도 간단해 지고 매번 인덱스의 시작이 1인지 구분하는 연산을 하지 않게 된다.