[백준] CLASS3 11659 구간 합 구하기4 - JAVA [자바]

안녕하세요. 이번에는 백준 11659 구간 합 구하기 4 문제를 풀어보려고 합니다.

 

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

11659번: 구간 합 구하기 4

---

Problem

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

 

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데인출하는 데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

사진 1. 문제

---

Solution

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static int[] arr;
    
    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());
        arr = new int[N + 1];
        
        st = new StringTokenizer(br.readLine(), " ");
        arr[0] = 0;
        for(int i = 1; i <= N; i++) {
            arr[i] += Integer.parseInt(st.nextToken()) + arr[i - 1];         
        }
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int start = Integer.parseInt(st.nextToken());       
            int end = Integer.parseInt(st.nextToken());         

            int sum = arr[end] - arr[start - 1];
            sb.append(sum).append("\n");
        }
        
        System.out.println(sb.toString());
    }
}

 이번 문제는 입력이 구간의 합을 구하는 문제이다. 여기서 핵심은 1 ≤ N ≤ 100,000 와 1 ≤ M ≤ 100,000의 조건과 시간제한 1초라는 문제가 있어서 이중 for문을 사용하면 안 된다. 그래서 배열을 선언한 후 배열의 자리마다 이전 배열값의 합들을 누적해서 배열에 넣으면 쉽게 문제를 해결할 수 있다.

 

1. 핵심 코드

// 배열의 자리마다 누적합을 저장하는 코드
for(int i = 1; i <= N; i++) {
	arr[i] += Integer.parseInt(st.nextToken()) + arr[i - 1];         
}
        
// 배열의 시작 지점과 끝 지점의 차를 이용해서 누적 합을 출력에 저장하는 코드       
for(int i = 0; i < M; i++) {
	st = new StringTokenizer(br.readLine(), " ");
            
	int start = Integer.parseInt(st.nextToken());       
	int end = Integer.parseInt(st.nextToken());         

	int sum = arr[end] - arr[start - 1];
	sb.append(sum).append("\n");
}

---

Performance

사진 2. 실행 결과