백준 11659 - 구간합 구하기 4

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

11659번: 구간 합 구하기 4

 

 

 

 

실패한 문제해석

---

처음 봤을 때는 그냥 "N개의 숫자의 사이에서 i-j까지의 구간합을 구한다."  라는 간단한 내용의 문제라는 것으로 파악했다.

이게 왜 실버문제일까 하고 고민을 하면서 일단 해보기로 했다.

 

그래서 로직을 간단하게 짰다.

 

1. Scanner로 N,M을 받는다.

2. N번 반복하면서 배열에 숫자들을 밀어넣는다.

3. M번 반복하면서 i,j를 받아서 i부터 j까지 구간에서 숫자를 더한다.

4. 출력

 

 

실패한 정답

---

 

import java.util.Scanner;

class Main {
  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();
    }

    // 구간 합 계산
    for (int i = 0; i < M; i++) {
        int startIndex = sc.nextInt();
        int endIndex = sc.nextInt();
        int sum = 0;

        // 유효한 구간의 합 계산
        for (int j = startIndex - 1; j < endIndex; j++) {
            sum += arr[j];
        }

        // 구간 합 출력
        System.out.println(sum);
    }  
  }
}

 

로직에 따라 충실하게 만들었다.

당연히 될줄 알았는데, 실패가 떴다.

실패 원인을 분석해보는데, 해당 문제의 제한시간은 1초, 그리고 입력받는 숫자 N은 1000개까지 허용이었다.

그러니까 1000나 되는 숫자를 Scanner로 받으려고 했다는점, 그리고 제한시간에 맞게 빠르게 계산이 이루어져야한다.

 

 

 

 

 

정답

---

 

찾아보니 구간 합 공식이라는 것이 존재했다.

숫자들의 리스트 A와 리스트A에 인덱스가 들어올 때마다 합을 해서 생기는  합배열 S를 준비한다.

 

S[j] - S[i-1]

 

이 공식을 이용하면 i과 j 사이의 구간합을 구할 수 있다.

 

예를들어 위의 사진에서 2부터 4까지의 값을 구하고 싶다고 하면

S[4] - S[1] = 48 - 28 = 20

A[2] + A[3] + A[4] = 20 

으로 구간합의 결과가 맞다. 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public 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]);
        }
    }
}

실패한 이유중에서 1000개의 숫자를 받을 수도 있기 때문에, Scanner보다 bufferedReader를 통해서 받도록 한다. 

그리고 한줄로 길게 들어오는 데이터를 받기위해서는 int보다 stringToeknizer를 이용한다. readLine()으로 해당 줄을 가져오고, nextToken으로 N, M을 받아준다. 

그리고 합배열을 담을 S를 만드는데, 배열에서 인덱스는 0부터 시작하기 때문에 나중에 i,j 사이의 구간합을 구할 때 고려하기 싫기 때문에 +1의 사이즈로 만들어 주었다. 

 

이후 숫자를 받아서 합배열 S를 만들어준다. 받을 값들을 계속 이전인덱스와 더해준다.

 

마지막으로 i,j를 받아서 구간합공식을 사용해준다. 이를 M번만큼 반복하면 된다.