문제

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

코드

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        final int N = Integer.parseInt(st.nextToken());
        final int M = Integer.parseInt(st.nextToken());

        int[] numberArr = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            numberArr[i] = numberArr[i-1] + Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int j = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            System.out.println(numberArr[k] - numberArr[j-1]);
        }
    }
}

생각

구간합 문제를 어떻게 푸는지 알게 되었다.
처음 풀이는 무식하게 더하는 범위를 읽을 때 마다 for문을 돌려서 합한 후에 출력했는데 시간초과가 계속 나가지고 수정을 반복하다 안되서 답을 찾아봤다.

범위를 받았을 때 합을 구하는게 아닌 배열에 값을 넣을 때 해당 위치의 수와 그 뒷 수를 합한 값을 넣고 범위를 받았을 때 끝위치의 수에서 시작위치의 뒷 수를 빼면 된다.

예시)
"5 4 3 2 1"의 수가 주어진다면
{0, 5, 9, 12, 14, 15} 구간합배열을 만든다.
주어진 합의 범위가 2 번째부터 4 번째까지 라면 4부터 2까지 합을 구하면 되는데 4부터 2까지의 합은 9다.
끝위치 4 -> 구간합배열[4]의 값은 14고
시작위치 2의 뒷 수 -> 2 - 1 = 1 구간합배열[1]의 값은 5 이므로 14 - 5 = 9 가되어 정답이 된다.

쉬운 문제라 생각했지만 시간제한으로 인해 통과를 못 하니 머리가 하얗게 되어버렸었다.
문제를 풀기 위해 이론 공부도 있지만 문제를 많이 풀어봐야겠다.
답지를 보고 풀었지만 나중에 다른 문제에 적용할 수 있다면 그게 내 실력이 됐다고 생각한다. 오늘부터 하루에 한 문제씩은 꼭 풀어야겠다.