카테고리: 구간합

문제

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

입력 조건

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제입력
5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력
12
9
1

1차 풀이 방식

1.누적합 배열을 만든다.

int[] acc = new int[N];
acc[0] = arr[0];
for(int i = 1; i < N; i ++){
	acc[i] = acc[i-1] + arr[i];
}

2.구간합을 구하는 함수를 만든다

public  static int sum(int[] acc, int i, int j) {
	if( i ==0 ){
    	return acc[j];
    }
    return acc[j] - acc[i-1];
}

1차 코드

import java.util.Arrays;
import java.util.Scanner;

class Main {
    public  static int sum(int[] acc, int i, int j) {
        if( i ==0 ){
            return acc[j];
        }
        return acc[j] - acc[i-1];
    }

    public static void main (String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 수의 개수
        int M = sc.nextInt(); // 문제 횟수

        // 배열 만들기
        int[] arr = new int[N];
        for(int i=0; i < N; i++){
            arr[i] = sc.nextInt();
        }


        // 누적합 배열 만들기
        int[] acc = new int[N];
        acc[0] = arr[0];
        for(int i = 1; i < N; i ++){
            acc[i] = acc[i-1] + arr[i];
        }

        // 문제횟수만큼 구간 합 구해서 출력
        int[] answer = new int[M];
        for(int k = 0; k < M; k++){
            int i = sc.nextInt() - 1;
            int j = sc.nextInt() - 1;
            answer[k] = sum(acc, i , j);
        }

        for(int k = 0; k < M; k++){
            System.out.println(answer[k]);
        }



    }
}

2차 풀이 방식

앞의 1차 풀이에서는 index가 0베이스여서 로직짜는데 헷갈림이 많았다.
인덱스를 1부터 베이스잡고 시작하면 좀 더 편할 것 같다.

2차 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

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 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] + Integer.parseInt(stringTokenizer.nextToken());
        }

        for(int q=0; q < quizNo; 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]);
        }

    }
}