문제
해결 방안 고민
•
구간 합을 구해야 하므로 누적 합의 개념을 활용하면 문제가 풀릴 것이라고 생각했다.
•
하지만 시간 초과가 발생했고 결론적으로는 다른 방법을 찾아야 했다.
•
문제의 답은 쉽게 찾을 수 있는 문제였으나 문제에 대한 접근을 어떻게 하느냐에 따라 통과/미통과가 결정되는 문제였다.
해결 방법
[ 첫 번째 방법 ]
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5
[ 두 번째 방법 ]
1
1+2
3+3
6+4
10+5
•
나는 여기서 첫 번째 방법을 활용해서 풀었는데 이중 for문으로 처리해야 하기에 O(N^2)의 시간 복잡도를 가진다. 그러므로 제출했을 때 시간 초과가 나왔다.
•
두 번째 방법은 하나의 for문으로 처리하면 되므로 O(N)의 시간 복잡도를 가진다. 그러므로 제출했을 때 시간 초과가 걸리지 않았다.
코드
•
시간 초과 코드
package algo250227;
import java.io.*;
import java.util.*;
// 구간 합 구하기 4 - 실버 3
public class Baek11659 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 누적 합 계산
int sum = 0;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
for (int j = start - 1; j <= end - 1; j++) {
sum += arr[j];
}
bw.write(String.valueOf(sum));
bw.newLine();
sum = 0;
}
bw.flush();
bw.close();
br.close();
}
}
Java
복사
•
통과 코드
package algo250227;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Baek11659_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 누적합 구하기
int[] prefixSum = new int[N + 1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= N; i++) {
prefixSum[i] = prefixSum[i - 1] + Integer.parseInt(st.nextToken());
}
// 구간합 계산
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
bw.write(String.valueOf(prefixSum[end] - prefixSum[start - 1]));
bw.newLine();
}
bw.flush();
bw.close();
br.close();
}
}
Java
복사
정리
확실히 이런 문제들을 보면 뭔가 정해진 패턴이 있다. 배열을 선언할 때 요소를 고려해 N + 1로 길이를 정하여 문제풀이를 진행한다. 누적 합 관련 문제를 풀 때 이 점을 고려하여 문제에 접근하면 풀이과정에서 방황하지 않을 것 같다.