[백준] 30960: 조별 과제 - JAVA

https://www.acmicpc.net/problem/30960

 

풀이

N명의 학생들의 조를 편성해야한다.

 

1개의 조만 3명으로 편성되고 다른 조들은 2명으로 편성된다.

 

학생에게 숫자가 부여되는데 각 조 안에서 (최댓값 - 최솟값)이 해당 조의 어색함이 된다.

 

어색함의 합의 최소가 되도록해야한다.

 

먼저 입력받은 배열을 정렬했다. 정렬 후 2개의 배열을 만들어서 하나는 앞에서부터 시작, 하나는 뒤에서부터 시작하여 누적합을 담았다.

 

누적합은 어색함들의 합을 더해줬다. `left[i] += (arr[i] - arr[i-2])` 이런식으로 어색함을 더해줬고, i는 2찍 증가시키면서 진행했다.

 

누적합 배열 2개를 만든 후, 어느 지점에서 3명인 조를 시작해야 어색함이 최소가될지 구해줬다.

 

 

---

 

메모리: 84096KB
시간: 912ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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

        int[] left = new int[n];
        for (int i = 1; i < n; i += 2) {
            left[i] += (arr[i] - arr[i - 1]);
            if (i - 2 >= 0) {
                left[i] += left[i - 2];
            }
        }

        int[] right = new int[n];
        for (int i = n - 2; i > 0; i -= 2) {
            right[i] += (arr[i + 1] - arr[i]);
            if (i + 2 < n) {
                right[i] += right[i + 2];
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int i = 0; i < n - 2; i += 2) {
            int tmp = (arr[i + 2] - arr[i]);
            if (i - 1 >= 0) {
                tmp += left[i - 1];
            }
            if (i + 3 < n) {
                tmp += right[i + 3];
            }
            answer = Math.min(tmp, answer);
        }

        System.out.println(answer);
    }
}