[ALGO#9] 백준_11659_실버3_구간 합 구하기4 : 구간합 [JAVA]

문제 링크

11659번: 구간 합 구하기 4

 

TMI) 백준 solved.ac에서 중간에 1월 18일 문제 풀었는데 왜 다음날로 문제가 누적되었는지 모르겠네요.. 내 연속 기록 살려내!!! (백준 기록에는 잘 뜨는데 무슨 문제인지 파악해 봐야겠습니다)

+) 18일날 처음 AC 받으신게 오전 4시 39분이고 이는 솔브드에선 17일로 판정됩다고 합니다. (즉 solved.ac는 백준 잔디랑 별개로 24시 기준이 아니라 오전 6시 기준으로 기록이 된다고 합니다)

+) 그니까 UTC+3(모스크바 시간대) 기준으로 갱신된다고 보시면 됩니다. 이유는 러시아가 코드포스의 나라라서?!

+) 새벽 4시에 문제 풀었더니 붕변 당했네요

 

 

구간합(=누적 합) 문제는 코테에서 빈출 유형입니다.

이 공식만 이해하고 있으면 쉽게 문제를 풀 수 있었습니다.

문제 요구 사항이 바뀔 수 있으니 암기보다는 원리를 이해하세요

// 구간합 공식 = 이전까지의 누적합 + 현재 값
			sums[i] = sums[i-1] + nums[i];
            
            
// 해당 범위의 구간합 = 해당 범위 마지막 인덱스 구간합 - 시작부붙 전의 인덱스 
			sum = sums[idx2] - sums[idx1-1];

 

시간 복잡도

최대 10만개짜리 배열에서, 최대 10만개의 질문에 대해 i번째부터 j번째 까지의 합을 출력해야 한다.
  1 <= i <= j <= N 이므로, 사실상 위 반복문은 최악의 경우 N번이 돌게되므로 getRangedSum 함수는 O(N)이 필요하다. 그리고 함수가 총 M번 불릴 것이므로 O(MN) 이라는 시간복잡도가 필요하다.

 

주의사항

arr[N]의 값은 결국 입력으로 주어진 모든 수의 합이 된다. 따라서 자료형에 따른 오버플로우를 주의해야한다(음수 표현범위 이하로 내려가는 것도 오버플로우). 예를들어 이 글에서 예시로 들었던 '구간 합 구하기 4' 문제의 경우 N은 최대 10^5이고, 각 값은 최대 1000 이므로, 모두 합쳐봐야 최대 10^8이라서 int 자료형으로 표현해도 아무런 문제가 없었다. 이처럼 최대값을 생각해보고 자료형을 구해 누적합을 계산해줘야 한다. 

 

성능 요약

메모리: 71432 KB, 시간: 1976 ms

분류

누적 합(prefix_sum)

 

전체 코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	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 count = Integer.parseInt(st.nextToken());
		int[] nums = new int[N+1];
		int[] sums = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) { // 1부터 처리하면 0인덱스의 i-1을 따로 처리 안해도 됨
			nums[i] = Integer.parseInt(st.nextToken());
			// 구간합 공식 = 이전까지의 누적합 + 현재 값
			sums[i] = sums[i-1] + nums[i];
		}
		
		// 해당 범위의 구간합 구하기
		int sum;
		for (int i = 1; i <= count; i++) {
			st = new StringTokenizer(br.readLine());
			int idx1 = Integer.parseInt(st.nextToken());
			int idx2 = Integer.parseInt(st.nextToken());
			// 해당 범위의 구간합 = 해당 범위 마지막 인덱스 구간합 - 시작부붙 전의 인덱스 
			sum = sums[idx2] - sums[idx1-1];
			System.out.println(sum);
		}	
	}
}

 

혹시 잘못된 정보나 궁금하신 내용이 있으시면 댓글로 남겨주시면 감사드리겠습니다.