[백준 Baekjoon] 11441번 합 구하기 - JAVA 문제 풀이 이 문제를 풀기 전에 누적 합이 먼지 알아야합니다. 문제에서 구간의 합을 출력하라 하였는데, 구간의합 = 누적 합이라고 생각하시면 됩니다. 누적 합은 이름에서 알 수 있듯이 일정 구간의 값들을 누적한 합입니다. 누적 합을 사용하는 이유는 구하고자하는 구간의 합을 매번 구하게 되면 O(n^2)의 시간복잡도를 갖기 때문에 이번 문제와 같이 최대 100,000 개의 수들을 100,000 구간의 합을 구하면 너무 큰 비용이 발생하게 됩니다. 누적합을 사용하면 구간의 합을 O(n)으로 구할 수 있습니다. 구간의 합을 구하기 앞서 누적합을 구해줍니다. int[] sum = new int[N + 1]; StringTokenizer st = new..