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

🔺 문제

11659번: 구간 합 구하기 4

 

🔺 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
	    var br = new BufferedReader(new InputStreamReader(System.in));
	    var st = new StringTokenizer(br.readLine(), " ");
	    
	    int n = Integer.parseInt(st.nextToken());
	    int m = Integer.parseInt(st.nextToken());
	    int[] arr = new int[n];     // N개의 수
	    int[] sumArr = new int[n];  // 구간 합 배열
	    
	    // N개의 수
	    st = new StringTokenizer(br.readLine(), " ");
	    for(int i = 0 ; i < n ; i++) {
	        arr[i] = Integer.parseInt(st.nextToken());
	    }
	    
	    // 구간 합 구하기
	    sumArr[0] = arr[0];
	    for(int i = 1 ; i < n ; i++) {
	        sumArr[i] = sumArr[i-1] + arr[i];
	    }
	    
	    // 구간 i,j
	    for(int i = 0 ; i < m ; i++) {
	        st = new StringTokenizer(br.readLine(), " ");
	        
	        int a = Integer.parseInt(st.nextToken()) -1;
	        int b = Integer.parseInt(st.nextToken()) -1;
	        
	        if(a == 0) {
	            System.out.println(sumArr[b]);
	        } else {
	            System.out.println(sumArr[b] - sumArr[a - 1]);
	        }
	    }
	}
}

✅ 해결 아이디어
- 구간 합 / 누적 합
- 구간 시작점이 1일 경우 출력 결과 따로 처리

맞긴 맞았는데 메모리 넘 크고 반복문을 세번이나 돌렸다,,,,ㅋ

효율적인 코드를 찾아서,,,,,~

---

🔺 다른 풀이들

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

[구간합, JAVA]백준 - 11659번

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

public class Main {
	public static void main(String[] args) throws IOException {
	    var br = new BufferedReader(new InputStreamReader(System.in));
	    var st = new StringTokenizer(br.readLine(), " ");
	    
	    int n = Integer.parseInt(st.nextToken());   // 표 크기
	    int m = Integer.parseInt(st.nextToken());   // 반복 휫수
	    int[] sum = new int[n+1];
	    
	    st = new StringTokenizer(br.readLine(), " ");
	    for(int i = 1 ; i <= n ; i++) {
	        sum[i] = sum[i-1] + Integer.parseInt(st.nextToken());
	    }
	    
	    for(int i = 0 ; i < m ; i++) {
	        st = new StringTokenizer(br.readLine(), " ");
	        int a = Integer.parseInt(st.nextToken());
	        int b = Integer.parseInt(st.nextToken());
	        
	        System.out.println(sum[b] - sum[a-1]);
	    }
	}
}

누적합 계산은 한 번만 하시고, 필요한 부분 뽑아쓰셨다.

입력과 동시에 누적합을 구해서 저장하시는..!! (누적합 배열 크기는 n + 1로 하고, 반복문에서 i 시작 범위는 1부터 시작하게)

다음엔 꼭 이렇게 해야지....!!!!

 

 

---

(+ 6/7 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static long[] arr, sum;
    static int s, e;
    static long result = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        StringBuilder sb = new StringBuilder();
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        arr = new long[N + 1];
        sum = new long[N + 1];
        
        // 숫자 배열 arr 입력받기
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 구간 합 배열 sum 채우기
        sum[1] = arr[1];
        for(int i = 2 ; i <= N ; i++) {
            sum[i] = sum[i-1] + arr[i];
        }
        
        // 구간 값 입력 받아 결과 출력하기
        for(int i = 0 ; i < M ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());
            
            result = (s == e) ? arr[s] : (sum[e] - sum[s - 1]);
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}