백준 11441번: 합 구하기

문제 설명

• https://www.acmicpc.net/problem/11441
• 구간의 누적합을 구하는 문제입니다.

접근법

• A부터 B까지의 누적합 = 0부터 B까지의 누적합 - 0부터 A-1까지의 누적합
• 크기가 N인 배열을 만드는 것보다 크기가 N+1인 배열을 만드는 게 더 편리합니다.
  • -1을 하기 때문에 0번째 칸을 0으로 비워두면 편리합니다.

정답

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		st = new StringTokenizer(br.readLine());
		int[] cumSum = new int[N + 1];
		for (int i = 1; i < N + 1; i++) {
			cumSum[i] = Integer.parseInt(st.nextToken()) + cumSum[i - 1];
		}
		int M = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			sb.append((cumSum[to] - cumSum[from - 1]) + "\n");
		}
		System.out.println(sb.toString());
	}

}

기타

• 입력과 출력이 많은 문제는 입/출력 방법에 따라 시간복잡도 차이가 많이 납니다.

1. Scanner, System.out.println사용
   

2. Scanner, StringBuilder사용
   

3. BufferedReader, StringBuilder사용