[백준 / Java] 11659번: 구간 합 구하기 4 (실버3)

문제 풀이 날짜: 2023.05.15
포스트 작성일: 2023.05.18

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 11659번: 구간 합 구하기 4 (실버3) (문제 링크)

 

키워드

구간 합

 

풀이 접근법

• 평범하게 중첩 for문으로 합을 구하면 시간초과가 된다. (N ≤ 10^5, M ≤ 10^5, N*M ≤ 10^10)
• DP와 유사한 발상에서 출발한다. 구했던 값을 또 구할 수도 있기 때문에 미리 배열의 합을 저장해놓는 것이 중요하다.
• 1부터의 k까지의 합을 미리 배열에 저장해놓고 중간 구간의 부분 합 = 큰 구간의 부분 합 - 작은 구간의 부분 합의 형태로 원하는 답을 구한다. 
  • 예를 들어, 3부터 7까지의 합을 구하고 싶다면 (1부터 7까지의 합) - (1부터 2까지의 합)을 구한다.
  • 이렇게 하면 O(N + M) 시간만에 답을 구할 수 있다.

 

코드

import java.io.*;
import java.util.*;

public class Q11659 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");

		int N = Integer.parseInt(temp[0]);
		int M = Integer.parseInt(temp[1]);
		
		int[] numbers = new int[N + 1];
		int[] sum = new int [N + 1];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i = 1; i <= N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
			sum[i] = sum[i - 1] + numbers[i];
		}
		
		StringBuilder sb = new StringBuilder();
		while(M-- > 0) {
			temp = br.readLine().split(" ");
			
			int start = Integer.parseInt(temp[0]);
			int end = Integer.parseInt(temp[1]);
			
			int sumOfSections = sum[end] - sum[start - 1];
			
			sb.append(sumOfSections).append('\n');
		}
		
		System.out.print(sb);
	}

}

---

 

매우 쉬운 문제이지만, 구간 합에 대한 이해가 없다면 시간초과를 받고 헤멜 수도 있다고 생각한다. 이런 스킬은 기초를 잘 알아두면 후에 여러 문제에 응용할 수 있으므로 잘 공부해두는 것이 좋겠다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day2/Q11659.java