11659번 : 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

 

문제

 

 

코드

import java.io.*;

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));

        String []input = br.readLine().split(" ");
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(input[0]); int m = Integer.parseInt(input[1]);
        input = br.readLine().split(" ");
        int num[] = new int[n+1];
        for(int i=0;i<n;i++) {
            int k = Integer.parseInt(input[i]);
            num[i+1] = k+num[i];
        }

        String w = "";
        for(int i=0;i<m;i++) {
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);

            sb.append((num[y]-num[x-1])+"\n");
        }
        bw.write(sb+""); bw.flush();
    }
}

 

 

해결방법

처음에 합계를 구하는 방법으로 제출하였는데 역시나 시간 초과가 났다.

어떻게 풀까 계속 고민해봤지만 방법이 떠오르지 않아 다른 사람의 풀이를 참고했다.

 

x~y 구간의 합 => y까지 더한 누적합 - (x-1)까지 더한 누적합

누적합을 이용하여 풀어야하는 문제였다. 구현은 쉬워서 구현하여 제출했지만 또 시간 초과가 났다.

첫 번째 이유는 출력할 문자열을 만들 때 StringBuilder를 쓰지 않았다.

String+= 는 할 때마다 메모리를 새로 만드므로 느리다. 반면에 StringBuilder는 메모리 옆에 쭉쭉 붙이므로 훨씬 빠르다.

두 번째 이유는 BufferedWriter를 쓰지 않았다.

BufferedWriter는 System.out.println() 보다 훨씬 빠르다. 이 점은 알고 있었지만 활용하지 못하였다. 정신을 잘 잡고 문제를 풀어야겠다.