백준 11659번 구간 합 알고리즘 이용

11659번

구간 합 알고리즘 이용

풀이는 아침에 쓰겠습니다!

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // System.in으로 콘솔에서 데이터 입력 받음
        //Inputstream 객체로 1byte만 읽을 수 있어서
        //InputStreamReader를 사용하게 된다.

        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());

        // N개의 수를 입력 받아 배열에 저장하기
        //일단 공백으로 수 구분하기
        int[] Arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            Arr[i]=Integer.parseInt(st.nextToken());
        }

        // 합배열 생성 코드 잘 기억하기!
        int[] Sum = new int[N+1];
        Sum[0]=0; // 1개
        for(int i=1; i<N+1; i++) // N개
        {// 1+N
            Sum[i]=Sum[i-1]+Arr[i-1];
        } // p.46과 좀 다른 부분 찾아서 분석해보기!
        //배열 대입은 상수처럼 취급되어서 시간 복잡도 계산에 제외?

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // 개수만큼 구간 합 구하기 반복 M번 반복
        for(int i=0; i<M; i++)
        {
            // 여기에 구간 합 구하기 1번 할 때의 process 적어주기
            int X,Y; // 구간 받기

            // 세트인거 잊지 마세요
            StringTokenizer stt = new StringTokenizer(br.readLine());
            X = Integer.parseInt(stt.nextToken());
            Y = Integer.parseInt(stt.nextToken());

            int result;
            result=Sum[Y]-Sum[X-1];
            bw.write(String.valueOf(result));
            if(i!=M-1)
                bw.write("\n");
        }

        // 아래 닫기 세트도 꼭 하기!
        bw.flush();
        bw.close();

    }
}

 

다른 문제-이걸 2차원 배열로 확장하면?!