문제

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

분석

작성해야할 코드를 단계별로 생각해 본다.

1. N(수의 개수), M(합을 구해야 하는 횟수)를 입력받는다.
2. N개의 수 입력과 동시에 누적 합을 저장하는 배열을 생성한다.
3. M번 반복문을 통해 i부터 j까지의 구간 합을 출력한다. 이때, i와 j는 M번 입력받는다.

소스코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 1. 입력
        // N (데이터의 개수), M(합을 구해야하는 횟수)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 2. N개의 숫자 입력과 동시에 합배열 구하기
        // S[i] = S[i-1] + A[i]
        st = new StringTokenizer(br.readLine());
        int[] S = new int[N+1];
        for(int i=1; i<N+1; i++) {
            S[i] = S[i-1] + Integer.parseInt(st.nextToken());
        }

        // 3. 합배열을 이용해서 구간 합 구하기
        // 구간 합 = S[j] - S[i-1]
        // sNum(구간합의 시작), eNum(구간합의 끝)
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int sNum = Integer.parseInt(st.nextToken());
            int eNum = Integer.parseInt(st.nextToken());
            System.out.println(S[eNum] - S[sNum-1]);
        }
    }
}

풀이 정리

Tip 1. bufferedReader 사용

입력 데이터가 많을 경우 Scanner보다 BufferedReader를 사용하는 것이 속도가 더 빠르다.

Tip 2. 누적 합 배열을 이용해서 구간 합을 구하는 방법

1) 누적 합 배열 구하기

S[i] = S[i-1] + A[i]

배열 A가 다음과 같을 때, 누적 합 배열을 계산하는 과정이다. 이때, 계산을 편하게 하기 위해 인덱스는 1부터 시작하도록 한다.

2) 구간 합 구하기

S[j] - S[i-1]

A[i] 부터 A[j] 까지의 합을 구할 경우 '구간 합'을 사용한다. 구간 합 계산을 위해 합배열을 사용한다.

Reference

[book] Do it! 알고리즘 코딩 테스트 - 자바 편