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

백만년만에 코테를 풀어봤습니다... (앞으로 꾸준히 풀자) 

 

 

 

✍️풀이방식

 

1초에 1억번 연산 -> 0.5초면 5천만번 연산이 일어난다는 뜻 

데이터의 범위가 100,000을 넘어가는 것을 주의하면서 풀 것! 

 

합 배열을 이용한 구간합을 사용해서 문제를 풀 것 

 

합배열, 구간합 공식 

S[i] = S[i-1]+A[i]   // S가 합배열 
S[j]-S[i-1] // 구간합 공식 

 

 

또한 받는 데이터의 양이 많기 때문에 Scanner가 아닌 Buffer로 구현할 것 (까먹지 말기...)

 

 

---

 

 

 

🖥️문제풀이

 

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

public class Main
{
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());//StringTokenizer로 값 분리 
	    int N = Integer.parseInt(st.nextToken()); //숫자 개수 
	    int M = Integer.parseInt(st.nextToken());//질의 개수 
	    long[] S = new long[N+1]; 
	    st = new StringTokenizer(br.readLine());
	    
	    for(int i=1; i<=N; i++){
	        S[i]=S[i-1] + Integer.parseInt(st.nextToken());
	    }//합 배열 저장 
	    
	    for(int q=0;q<M;q++){
	          st = new StringTokenizer(br.readLine());
	          int i=Integer.parseInt(st.nextToken());
	          int j=Integer.parseInt(st.nextToken());
	          System.out.println(S[j]-S[i-1]);//구간합 출력 
	    }
	     

	}
}

 

 

 

 

☑️실행결과