구간 합 구하기

문제 (시간제한 : 1초)

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

문제부터 이해가 잘 안됀다 ㅠㅠ

예제 입력 1로 문제를 설명해보면

5  3      <--- 5 : 데이터 개수, 3 : 구할 문제 개수
5  4  3  2  1    <--- 데이터 5개
1  3    <--- 문제 : 1번째 ~ 3번째 수의 합을 구하세요(5 + 4 + 3)
2  4    <--- 문제
5  5    <--- 문제

이렇다

 

 

내 풀이

public class Main
{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int num = Integer.parseInt(st.nextToken());
        int quizNum = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[num];
        
        for (int i = 0; i < num; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int sum;
        for (int i = 0; i < quizNum; i++) {
            sum = 0;
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken()) - 1;
            int num2 = Integer.parseInt(st.nextToken()) - 1;
            for (int j = num1; j <= num2; j++) {
                sum += arr[j];
            }
            
            bw.write(String.valueOf(sum) + "\n");
        }
	    bw.flush();
	    bw.close();
	    br.close();
	}
}

처음에 이렇게 짰는데 시간 초과가 났다.

첫번째 줄에 들어갈 수 있는 수의 최대가 100000이니까 위에서 내가 짰던 방식대로 하면 최악의 경우 1 ~ 100000까지 더해야 한다.

그래서 시간초과가 난 것 같다.

 

이런 문제에서는 합 배열 공식과 구간 합 공식을 사용해야한다.

<합 배열 공식>

S[i] = S[i - 1] + A[i]
* S는 1 ~  i번째 원소까지의 배열의 합을 뜻하고, A[i]는 i번째 원소값을 뜻한다. 

 

<구간 합 공식>

S[a] - S[i - 1]
* i에서 a까지의 합

이건 이미지로 생각하면 더 편하다.

세번째 ~ 마지막째 합을 구하려면

전체 - (5 + 4)를 해주면 된다.

 

이 방식으로 예제 문제1을 풀어보면

2 4 : S[4] - S[1] = 14 - 5 = 9

이렇게 된다.

 

수정한 코드

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

public class Main
{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	    
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int num = Integer.parseInt(st.nextToken());
        int quizNum = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int[] sum = new int[num + 1];
        sum[0] = 0;
        for (int i = 1; i <= num; i++) {
            sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
        }
        
        for (int i = 0; i < quizNum; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());
            
            bw.write(String.valueOf(sum[num2] - sum[num1 - 1]) + "\n");
        }
	    bw.flush();
	    bw.close();
	    br.close();
	}
}