[백준/자바] 11659 구간 합 구하기 4

[백준/자바] 11659 구간 합 구하기 4

 

📌 문제 

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

 

 

⚔ 입력

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

 

 

📣 출력

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

 

 

 

 

---

 

 

 

💎 문제분석하기

 

구간 합을 구하는 문제는 배열의 순차적 진행에서 합을 구하는 방식으로 할 수 있다. 

합 배열은 S[i] = S[i-1] + A[i]이다.

 

따라서 특정 구간까지의 합을 구하는 공식은 

S[i] - S[j]로 표현된다. 

 

1 2 3 4 5 6 

--- (1)

-------------- (2)

 

S(2)에서 S(1)을 뺀 만큼에서 해당 구간의 합이 구해진다. 

 

구간합을 이처럼 구하지 않고 매번을 계산한다면 최악의 경우 1억 회 이상의 연산이 수행되어 1초 이상의 수행 시간이 필요해진다. 

 

 

 

📜 슈도코드 작성하기 

 

N개의 배열을 받음과 동시에 합 배열을 생성한다. 

 

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

 

구간이 주어지면 해당 구간에 따른 공식을 쓴다. 

 

S[j] - S[i-1] 

 

 

 

숫자 개수 = NumberCounts

질의 개수 = QuizCounts 

 

for 숫자 개수만큼 반복하며 합배열 생성 

 

for 질의 개수만큼 반복하며

질의 범위를 받고 

구간 합 출력 

 

 

💡 코드 구현하기

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		int numberCounts = Integer.parseInt(stringTokenizer.nextToken());
		int quizCounts = Integer.parseInt(stringTokenizer.nextToken());

		long[] S = new long[numberCounts + 1];        // 0번째 것에서 -1이 되어버리니까 1번재부터 반복문을 돌리기 위해

		stringTokenizer = new StringTokenizer(bufferedReader.readLine());

		// 합 배열 생성하기
		for (int i = 1; i <= numberCounts; i++) {
			S[i] = S[i - 1] + Integer.parseInt(stringTokenizer.nextToken());
		}

		// 질의 개수 만큼 돌면서 새롭게 들어오는 입력을 받고 해당 범위로 설정된 구간합 출력
		for (int q = 0; q < quizCounts; q++) {
			stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			int i = Integer.parseInt(stringTokenizer.nextToken());
			int j = Integer.parseInt(stringTokenizer.nextToken());
			System.out.println(S[j] - S[i - 1]);
		}

	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편