๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

[๋ฐฑ์ค€ ๋ˆ„์ ํ•ฉ] 11659๋ฒˆ: ๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 4

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2024. 1. 14.

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

 

11659๋ฒˆ: ๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 4

์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N๊ณผ ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ํšŸ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜๋Š” 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์…‹์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์—๋Š” ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ๊ตฌ๊ฐ„ i์™€ j

www.acmicpc.net

๊ตฌ๊ฐ„ ํ•ฉ ๊ตฌํ•˜๊ธฐ 4 ์„ฑ๊ณต

 
 
์‹œ๊ฐ„ ์ œํ•œ๋ฉ”๋ชจ๋ฆฌ ์ œํ•œ์ œ์ถœ์ •๋‹ต๋งžํžŒ ์‚ฌ๋žŒ์ •๋‹ต ๋น„์œจ
1 ์ดˆ 256 MB 101082 41558 30954 39.014%

๋ฌธ์ œ

์ˆ˜ N๊ฐœ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ์ˆ˜์˜ ๊ฐœ์ˆ˜ N๊ณผ ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ํšŸ์ˆ˜ M์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” N๊ฐœ์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ˆ˜๋Š” 1,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์…‹์งธ ์ค„๋ถ€ํ„ฐ M๊ฐœ์˜ ์ค„์—๋Š” ํ•ฉ์„ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ๊ตฌ๊ฐ„ i์™€ j๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ด M๊ฐœ์˜ ์ค„์— ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ i๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ j๋ฒˆ์งธ ์ˆ˜๊นŒ์ง€ ํ•ฉ์„ ์ถœ๋ ฅํ•œ๋‹ค.

์ œํ•œ

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

์˜ˆ์ œ ์ž…๋ ฅ 1 ๋ณต์‚ฌ

5 3
5 4 3 2 1
1 3
2 4
5 5

์˜ˆ์ œ ์ถœ๋ ฅ 1 ๋ณต์‚ฌ

12
9
1

 

<<ํ’€์ด>>

 

-๋‚˜์˜ ํ’€์ด-

 

ํ  ์ผ๋‹จ ํด๋ž˜์Šค๋กœ ๋”ฐ๋กœ ๋งŒ๋“ค๊ณ  ๊ฐ์ฒด ์ด์šฉํ•ด์„œ ํ’€์—ˆ์ง€๋งŒ ์‹œ๊ฐ„์ดˆ๊ณผ์ด๋‹ค. 

import java.util.*;

class Sum {
    int first;
    int last;

    Sum(int first, int last) {
        this.first = first;
        this.last = last;
    }
}

class Main {
    private int[] solution(int[] arr, Sum[] brr) {
        int sum = 0;
        int[] answer = new int[brr.length];
        for(int i = 0; i < brr.length; i++){
            for(int j = brr[i].first; j <= brr[i].last; j++) {
                sum += arr[j - 1];
            }
            answer[i] = sum;
            sum = 0;
        }
        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Sum[] brr = new Sum[m];
        for(int i = 0; i < m; i++) {
            brr[i] = new Sum(in.nextInt(), in.nextInt());
        }

        for(int x : T.solution(arr, brr)){
            System.out.println(x);
        }

    }
}

 

 

-์ˆ˜์ •ํ•œ ์ฝ”๋“œ-

 

์›์ธ์„ ์ฐพ์„ ์ˆ˜ ์žˆ์—ˆ๋Š”๋ฐ ์ด์ค‘ for๋ฌธ์„ ๋Œ๊ณ  ์žˆ๋Š” ๋ถ€๋ถ„์—์„œ ๋ฌธ์ œ์˜€๋˜ ๊ฒƒ์ด๋‹ค. ๋‚˜๋ฆ„ ์ง์ž‘์€ ํ–ˆ์ง€๋งŒ, ์šฐ๋ฆฌ๋Š” ์ด๋•Œ 

"๋ˆ„์ ํ•ฉ"์„ ์ด์šฉํ•˜๋Š”๋ฐ, ์ด๋ฅผ ํ™œ์šฉํ•˜๋ฉด ์ด์ค‘ for๋ฌธ์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ์ฝ”๋“œ๋ฅผ ์งค ์ˆ˜ ์žˆ๊ณ , ์‹œ๊ฐ„์ดˆ๊ณผ์—์„œ ๋ฒ—์–ด๋‚  ์ˆ˜ ์žˆ๋‹ค.

import java.util.*;

class Sum {
    int first;
    int last;

    Sum(int first, int last) {
        this.first = first;
        this.last = last;
    }
}

class Main {
    private int[] solution(int[] arr, Sum[] brr) {
        int[] prefixSum = new int[arr.length + 1];
        for (int i = 1; i <= arr.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
        }

        int[] answer = new int[brr.length];
        for (int i = 0; i < brr.length; i++) {
            answer[i] = prefixSum[brr[i].last] -
                    prefixSum[brr[i].first - 1];
        }
        return answer;
    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        Sum[] brr = new Sum[m];
        for(int i = 0; i < m; i++) {
            brr[i] = new Sum(in.nextInt(), in.nextInt());
        }

        for(int x : T.solution(arr, brr)){
            System.out.println(x);
        }

    }
}

 

๋ˆ„์ ํ•ฉ์ด๋ž€

 

 

๋ฐฐ์—ด์— ์žˆ๋Š” ๊ฒƒ์„ ์ฒ˜์Œ ๋ถ€ํ„ฐ ๋ˆ„์ ํ•œ ๊ฒƒ๋“ค์„ ์ƒˆ๋กœ์šด ๋ฐฐ์—ด prefix๋ผ๋Š” ๊ณณ์— ๋„ฃ์–ด๋‘”๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋งŒ์•ฝ 3๋ฒˆ์งธ์—์„œ 5๋ฒˆ์งธ์˜ ๋ˆ„์ ํ•ฉ์„ ์•Œ๊ณ  ์‹ถ์œผ๋ฉด, 

23 - 9๋ฅผ ํ•˜๋ฉด ์‰ฝ๊ฒŒ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค.

 

์ด๋ฅผ ํ™œ์šฉํ•จ์œผ๋กœ์จ ์ด์ค‘ for๋ฌธ์œผ๋กœ ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(N^2) ์ด ๋  ์ˆ˜ ์žˆ๋Š” ๊ฒƒ์„ ๋‹จ์ˆœํžˆ ์‚ฌ์น™์—ฐ์‚ฐ ๋นผ๊ธฐ๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๊ฒŒ ๋จ์œผ๋กœ์จ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ O(N)์œผ๋กœ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค.

 

๋ˆ„์ ํ•ฉ ์ง์ด๋„ค ~~๐Ÿ˜

๋Œ“๊ธ€