[ 백준 11659 ] - 구간 합 구하기 4 (Java, Kotlin)

 

11659번: 구간 합 구하기 4

 

문제 이해 & 기본 개념

• N개 원소를 가진 배열이 있을 때, i~j 구간의 합을 구하는 문제
• N과 M이 최대 10만이므로, 매번 특정 구간의 합을 구하면 시간 초과 발생

최악의 경우

N = 100,000
M = 100,000 (입력으로 들어오는 구간의 수)

M(10만)개의 구간이 전부 (1~100,000)이라면 ?

N(10만)개의 원소의 합을 M(10만)번 구해야하므로 시간 복잡도는 O(nm) = O(n^2) (n과 m이 같은 경우)

즉, 100,000 x 100,000 = 10,000,000,000 (100억) 번의 연산을 거쳐야한다.

---

중요 포인트

• 중복 계산을 줄이는게 포인트
• 구간의 합을 미리 구해놓는 방법을 고려해야한다. (한 번만 계산하는 방법)

---

최종 풀이

1. 구간을 다른 방법으로 해석해본다.
   • (i~j)의 구간을 i번째 원소에서 j번째 원소까지의 합이라고 생각 x
   • (i~j)을 j까지 더한 값에서 i까지 더한 값을 뺀 값이라고 생각
2. 배열의 합을 누적시켜 저장해둔다.
   
   • sum[] 배열엔 해당 원소까지의 누적 합을 계산
   • sum[10]이면 10번째 원소까지 더한 값이 저장되는 것
3. sum[] 배열에서 구간의 합이 바로 구해진다.
   • sum[j] - sum[i-1]가 구간 (i~j)의 합이 된다.
   • 구간에선 i도 포함이므로 sum[i-1]임을 주의

---

소스 코드

 

자바(Java)

public class Main {
	static int[] num = new int[100_001];
	static int[] sum = new int[100_001];
	static StringBuilder sb = new StringBuilder();

	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());

    	st = new StringTokenizer(br.readLine());
    	for (int i = 0; i < n; i++) {
            num[i + 1] = Integer.parseInt(st.nextToken());
            sum[i + 1] = sum[i] + num[i + 1];
    	}

    	for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()); // 구간의 시작
            int e = Integer.parseInt(st.nextToken()); // 구간의 끝
    	    sb.append(-sum[s - 1] + sum[e]).append("\n");
    	}

    	System.out.print(sb.toString());
	}
}

 

코틀린(Kotlin)

val num = Array<Int>(100_001){0}
val sum = Array(100_001){0}
val sb = java.lang.StringBuilder()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var st = StringTokenizer(readLine())
    val n = st.nextInt()
    val m = st.nextInt()

    st = StringTokenizer(readLine())
    repeat(n){
        num[it+1] = st.nextInt()
        sum[it+1] = (sum[it] + num[it+1])
    }

    repeat(m){
        st = StringTokenizer(readLine()).apply {
            sb.append(-sum[nextInt()-1]+sum[nextInt()]).append("\n")
        }
    }

    print(sb.toString())
}

fun StringTokenizer.nextInt() = this.nextToken().toInt()