BOJ_S3_11659

📁 [S3_11659] 구간 합 구하기4

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

public class Main {
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine(), " ");
		
		// 개수
		int N = Integer.parseInt(st.nextToken());
		
		// 횟수
		int M = Integer.parseInt(st.nextToken());
		
		int[] arr =new int[N+1];
		int[] sum = new int[N+1];
		sum[0] = 0;
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=1; i<N+1; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
            // 합 구하기 
			sum[i] = arr[i] + sum[i-1];
		}
		
		
		for(int i=0; i<M; i++) {
		st = new StringTokenizer(br.readLine(), " ");
		
		// 시작과 끝
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
        // 전체 합을 빼기
		int res = 0;
		start -= 1;
		res = sum[end] - sum[start];
		
		sb.append(res).append("\n");
		
		}
		
		// 출력
		System.out.println(sb);
	}
}

🤔 나의 생각

처음에 시간복잡도를 안보고 바보같이 쉽다고 for문으로 그냥 풀었다.. ㅋㅋㅋㅋ
for문으로 찾는값 시작값에서 끝값 까지 다 더해주는 식으로. 제출했는데 한동안 채점이 진행이 안되길래 .. 설마? ㅋㅋ 너무쉽긴했다 이러면서 다시 돌아갔다.
돌아가서 보니 100000 개이다..ㅋㅋㅋ 무조건 시간초과.. O(N^2) 이였으니 1초안에는 불가능이였다..
그래서 보니 합을 누적해서 구해주고 합끼리 빼주면 시간복잡도가 O(N) 인 것이다.
그래서 입력 받을 때 sum 배열을 하나 더 해서 계속 합을 저장했다.
그러고 구해야 하는 끝값의 합에서 (시작 값 -1) 합을 빼주었다.
너무 만만하게 봤다가 한 대 얻어맞은 문제 ^^