문제
해결 방안 고민
입력 :
3
1 -2 3
=> x1x2x3
=> 1(arr[0]), -1(arr[0] + arr[1]), 2(arr[0] arr[1] + arr[2])
출력:
(x1x2) + (x1x3) + (x2x3)=
-2 + 3 + (-6)
-5
--- 누적 합 ---
투 포인터와 정렬?
ex) 1 2 3 4 5
12 13 14 15
23 24 25
34 35
45
Markdown
복사
•
처음에는 투 포인터와 정렬을 활용하면 풀리는 문제인 줄 알았다.
•
하지만 막상 투 포인터를 활용하여 풀어보니 계속해서 시간초과가 발생했다.
•
조건을 제대로 고려하지 못한 거 같아 long으로 형변환 했으나 그래도 여전했다.
package algo250219;
import java.io.*;
import java.util.*;
// 귀찮아(SIB) - 실버 5
public class Baek14929 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 값이 10만개, X의 최댓값인 100으로 모든 값이 입력될 령우 int 형 범위 넘어감을 고려
long answer = 0;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] prefixSum = new int[N + 1]; // 누적 합 배열
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int sum = 0;
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum += arr[i];
prefixSum[i + 1] = sum;
}
for (int i = 0; i < N; i++) {
int standard = arr[i];
int calculatedSum = prefixSum[N] - prefixSum[i + 1];
answer += (long) standard * calculatedSum;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
Java
복사
해결 방법
•
다시 고민하고 또 고민해봤고 결국 합 계산을 매번 구할 필요 없이 문제를 해결할 수 있다는 점을 알았다.
•
미리 누적합(prefixSum)을 구함으로써 매번 합 계산을 하지 않아도 된다.
arr
Index | 0 | 1 | 2 |
Value | +1 | -2 | +3 |
prefixSum
Index | 0 | 1 | 2 | 3 |
Value | 0 | +1 | -1 | +2 |
•
여기서 x2 + x3을 구하려면 prefixSum[3] - prefixSum[2 - 1] 을 하면 1이 나온다.
•
prefixSum[3] 은 arr[0]부터 arr[2]까지의 전체 합을 의미하고, PrefixSum[1]은 arr[0]까지의 합을 의미한다. 그래서 arr[1] + arr[2]의 값이 나온다.
•
조건을 고려해야 하기 때문에 long형 으로 답을 제출해야 한다.
•
prefixSum은 각 자리에서의 합을 의미하므로 N+1 만큼의 Size여야 한다.
•
즉, arr[0]까지의 누적합을 구하려면 prefixSum[0 + 1]을 구해야 한다.
•
arr[2]까지의 누적합을 구하려면 prefixSum[2 + 1]을 구해야 한다.
•
arr[1] + arr[2]의 합을 구하려면, arr[3] - arr[1]을 구하면 된다.
코드
•
시간 초과 코드
◦
일일이 합을 다 고려해서 계산
package algo250219;
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 Baek14929_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));
int N = Integer.parseInt(br.readLine());
long sum = 0; // 누적 합
int start = 0;
int end = start + 1;
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
while (end < N) {
sum += arr[start] * arr[end];
end++;
if (end == N) {
start++;
end = start + 1;
}
}
bw.write(String.valueOf(sum));
bw.flush();
bw.close();
br.close();
}
}
Java
복사
•
제출 통과 코드
◦
미리 누적 합을 구하여 매번 계산하지 않도록 구현
package algo250219;
import java.io.*;
import java.util.*;
// 귀찮아(SIB) - 실버 5
public class Baek14929 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 값이 10만개, X의 최댓값인 100으로 모든 값이 입력될 령우 int 형 범위 넘어감을 고려
long answer = 0;
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
int[] prefixSum = new int[N + 1]; // 누적 합 배열
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int sum = 0;
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum += arr[i];
prefixSum[i + 1] = sum;
}
for (int i = 0; i < N; i++) {
int standard = arr[i];
int calculatedSum = prefixSum[N] - prefixSum[i + 1];
answer += (long) standard * calculatedSum;
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
br.close();
}
}
Java
복사