[백준]-구간 합 구하기 4(JAVA)

구간 합 구하기 4 문제 바로가기

❓ 문제

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

✔ 제한 사항

• 시간 제한 : 1초
• 메모리 제한 : 256MB
• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

📌 입출력 예 및 입출력 설명

• 입력 : 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
• 출력 : 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

💡 풀이 방법

• 구간 합 공식을 이용하여 풀이
• 구간 합 공식 : S[j] - S[i-1] // i에서 j까지 구간 합

🔑 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] num = new int[N];
		int[] sNum = new int[N+1];
		
		for(int i = 0; i<num.length; i++) {
			num[i] = sc.nextInt();
		}
		sNum[0] = 0;
		
		for(int i = 1; i<sNum.length; i++) {
			sNum[i] = sNum[i-1] + num[i - 1];
		}
		
		for(int n = 0; n<M; n++) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			int sum;
			if(i==1) {
				sum = sNum[j];
			} else {
				sum = sNum[j] - sNum[i-1];
			}
			System.out.println(sum);
			
		}
	}

}

💯 해결완료