알고리즘
[Java] 백준 1549번 K
J3SUNG
2023. 8. 9. 02:41
728x90
누적합 문제입니다.
수열이 주어집니다.
[연속한 k개의 수1]와 [연속한 k개의 수2]의 차가 가장 적은 값을 구해야합니다.
위의 [연속한 수1] [연속한 수2]는 겹치면 안되며, 적은 값이 여러개면 k를 최대인것으로 출력합니다.
누적합을 구해준후에 브루트포스로 모든 경우의수를 확인했습니다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = null;
int n = Integer.parseInt(br.readLine());
long[] arr = new long[n + 1];
int k = 0;
long min = Long.MAX_VALUE;
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; ++i) {
int num = Integer.parseInt(st.nextToken());
arr[i] = arr[i - 1] + num;
}
for (int i = 1; i <= n / 2; ++i) {
for (int j = i; j <= n; ++j) {
for (int l = j + i; l <= n; ++l) {
long sub = Math.abs((arr[j] - arr[j - i]) - (arr[l] - arr[l - i]));
if (sub <= min) {
min = sub;
k = i;
}
}
}
}
bw.write(k + "\n");
bw.write(min + "\n");
bw.close();
}
}