[백준] 11659번 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

Solution 1.

문제에서 0번째 배열을 1번째 배열이라고 지칭하고 있다.

따라서, 0번째 배열을 비워두고 1번째 부터 값을 채워나가면 로직이 더 간편해진다.

 

예제를 대입하여 그림으로 이해하는 것이 빠르다.

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());	// "5 3" 입력

        int N = Integer.parseInt(st.nextToken());	// N = 5
        int M = Integer.parseInt(st.nextToken());	// M = 3

        long [] arr = new long[N+1]; // 합 배열 선언	

        // ---- st에서 token을 다 꺼냈으므로 st는 비어있음!

        st = new StringTokenizer(br.readLine());    // st에 새로운 문자열 입력
        // st = "5 4 3 2 1"
        
        for(int i=1; i<=N; i++){	// 합 배열 arr에 값 저장
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }
        

        // ---- st에서 token을 다 꺼냈으므로 st는 비어있음!

       
        for (int q=0; q<M;q++){
            st = new StringTokenizer(br.readLine());	// 구간 입력

            int q1 = Integer.parseInt(st.nextToken());
            int q2 = Integer.parseInt(st.nextToken());

            System.out.println(arr[q2]-arr[q1-1]);
        }

    }
}

 

 

Solution 2.

그냥 0번째부터 값을 저장하면 아래와 같다.

1번 처럼 하는 것이 훨씬 간편함을 알 수 있다.

 

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

       	long [] arr = new long[N];  // 합 배열 선언

        // ---- st에서 token을 다 꺼냈으므로 st는 비어있음!

        st = new StringTokenizer(br.readLine());    // st에 새로운 문자열 입력
        // st = "5 4 3 2 1"
        for(int i=1; i<=N; i++){
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }
        for(int i=0; i<N; i++){
            if (i == 0) {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            else{
                arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
            }

        }

        // ---- st에서 token을 다 꺼냈으므로 st는 비어있음!

        for(int q=0; q<M; q++){
            st = new StringTokenizer(br.readLine());
            int q1 = Integer.parseInt(st.nextToken());
            int q2 = Integer.parseInt(st.nextToken());
            if (q1 == 1){
                System.out.println(arr[q2-1]);
            }
            else{
                System.out.println(arr[q2-1] - arr[q1-2]);
            }

        }
    }
}

 

 

❓합 배열을 long형으로 선언한 이유

덧셈이나 곱셈 연산이 많을 때, int형으로 선언하면 범위를 초과하여 잘못된 값이 나올 수 있다.

따라서 long형으로 선언하는 것이 안전하다!

 

 

👩‍💻 BufferedReader, StringTokenizer 참고

https://happindex.tistory.com/26

Scanner보다 빠른 BufferedReader, StringTokenizer