[11649] 구간 합 구하기 4

✔ 구간 합 구하기 4

[백준 11649]

문제 분석하기

구간 합을 매번 계산한다면 100000 X 100000 가 되므로

최악의 경우 1억 회 이상의 연산을 수행하게 되어 0.5초 안에 모든 구간 합 계산을 끝낼 수 없음

그러므로 구간 합을 이용

손으로 풀어보기

1. N개의 수를 입력받음과 동시에 합 배열을 생성
2. 구간 i ~ j가 주어지면 구간 합을 구하는 공식으로 정답을 출력 

슈도코드 작성하기

suNo(숫자 개수), quizNo(질의 개수) 저장하기
for(숫자 개수만큼 반복하기) {
    합 배열 생성하기(S[i] = S[i - 1] + A[i])
}
for(질의 개수만큼 반복하기) {
    질의 범위 받기(i ~ j)
    구간 합 출력하기(S[j] - S[i - 1])
}

코드 구현하기

/**
 * 11659) 구간_합_구하기_4
 */
public class D003_11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        // suNo(숫자 개수), quizNo(질의 개수) 저장하기
        int suNo = Integer.parseInt(stringTokenizer.nextToken());
        int quizNo = Integer.parseInt(stringTokenizer.nextToken());
        long[] S = new long[suNo + 1];
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        // 숫자 개수만큼 반복하기
        for (int i = 1; i <= suNo; i++) {
            // 합 배열 생성하기(S[i] = S[i - 1] + A[i])
            S[i] = S[i - 1] + Integer.parseInt(stringTokenizer.nextToken());
        }
        // 질의 개수만큼 반복하기
        for (int q = 0; q < quizNo; q++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            // 질의 범위 받기(i ~ j)
            int i = Integer.parseInt(stringTokenizer.nextToken());
            int j = Integer.parseInt(stringTokenizer.nextToken());
            // 구간 합 출력하기(S[j] - S[i - 1])
            System.out.println(S[j] - S[i - 1]);
        }
    }

}