[백준/Java] 11659번 :: 구간 합 구하기 4

| 문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

| 입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

| 출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

| 풀이

- 실패 풀이 (시간 초과)

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

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());
        StringBuilder sb = new StringBuilder();

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] arr = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int x=0; x<M; x++)
            arr[x] = Integer.parseInt(st.nextToken());

        for(int y=0; y<N; y++)
        {
            st = new StringTokenizer(br.readLine());

            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());

            int sum = 0;
            for(int z=i-1; z<j; z++)
                sum += arr[z];
            sb.append(sum).append("\n");
        }
        System.out.println(sb);
    }    
}

 

- 정답 (누적 합)

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

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());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N+1];

        st = new StringTokenizer(br.readLine());
        for(int x=1; x<=N; x++)
            arr[x] = arr[x-1]+Integer.parseInt(st.nextToken());

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

            sb.append(arr[j] - arr[i-1]).append("\n");
        }

        System.out.println(sb);
    }
}

 

| 정리

처음에는 시간 초과로 풀이 실패,,,! 나도 풀면서 반복문이 너무 많아서 시간 초과 될 것 같다는 예상이 들기는 했다,,

그럼 어떻게 풀어야하나,,, 싶어서 다른 풀이를 찾아봤더니 누적합!!!!을 활용해서 푸는 문제라는 것을 파악했다.

이렇게 문제 푸는 스킬 +1 해나가기,,, 화이팅~!