[파이썬, Java] 11659. 구간 합 구하기 4

문제

수 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.io.*;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws Exception{
        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());     // 합
        int[] arr=new int[N];
        int[] total=new int[N+1];
        int start=0; int end= 0;
        st=new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        total[1]=arr[0];
        for(int i=2; i<=N; i++){
            total[i]=total[i-1]+arr[i-1];
        }

        for(int i=0; i<M; i++){
            st=new StringTokenizer(br.readLine());
            start=Integer.parseInt(st.nextToken());
            end=Integer.parseInt(st.nextToken());
            System.out.println(total[end]-total[start-1]);
        }
    }
}

다른 사람의 풀이를 참고했다.

배열에 i번까지의 합을 다 구한 뒤 구간합을 출력해야 시간초과가 안 난다.

 

 

# 시간초과
import sys
input=sys.stdin.readline
N, M=map(int, input().split())  # 수의 개수, 합
lst=list(map(int, input().split()))     # N개의 수

for _ in range(M) :
    start, end=map(int, input().split())
    start-=1
    end-=1
    total=0
    while start <= end :
        total+=lst[start]
        start+=1
    print(total)

투포인터 풀이

 

 

# 시간초과
import sys
input=sys.stdin.readline
N, M=map(int, input().split())  # 수의 개수, 합
lst=list(map(int, input().split()))     # N개의 수
part=[list(map(int, input().split())) for _ in range(M)]

for s, e in part :
    start=s-1
    end=e
    print(sum(lst[start:end]))

입력의 크기가 클때 역시 슬라이싱은 사용하는 게 아니다

슬라이싱은 O(N)이다(슬라이싱하는 요소의 갯수가 N).

sum()은 O(N)이다.

 

 

🎀 다른 사람 풀이

# https://donghak-dev.tistory.com/179?category=904697
import sys
input=sys.stdin.readline

N, M=map(int, input().split())  # 수의 개수, 합
arr=list(map(int, input().split()))
sum_arr=[0, arr[0]]

for i in range(1, len(arr)) :
    sum_arr.append(sum_arr[i]+arr[i])

for _ in range(M) :
    start, end=map(int, input().split())
    print(sum_arr[end]-sum_arr[start-1])

합을 미리 다 구해놓고 요청마다 합을 출력해야 한다.

[5, 4, 3, 2, 1]은 sum_arr=[0, 5, 9, 12, 14, 15]다.

sum_arr[i]는 arr의 i번째까지 합이다.(1부터 시작한다고 생각하고)

end번째 합에서 start 이전 합을 뺀 값을 출력한다.

대부분이 이 알고리즘으로 풀었다.

 

 

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

class Main {
    public static void main(String[] args) throws Exception{
        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());     // 합
        int[] memo=new int[n+1];
        st=new StringTokenizer(br.readLine());

        for(int i=1, sum=0; i<=n; i++){
            sum+=Integer.parseInt(st.nextToken());
            memo[i]=sum;
        }

        StringBuilder sb=new StringBuilder();

        while(m-- > 0){
            st=new StringTokenizer(br.readLine());
            sb.append(-memo[Integer.parseInt(st.nextToken())-1]
            + memo[Integer.parseInt(st.nextToken())]).append("\n");
        }
        br.close();
        System.out.print(sb);
    }
}

n개의 수를 입력받으면서 합계를 담는 momo 배열을 초기화한다.

StringBuilder에 추가했다가 while문이 끝난 후 한번에 출력한다.

 

 

문제 출처 👉 백준