[자바] 백준 16200 - 해커톤 (java)

목차

문제 : boj16200

 

 

필요 알고리즘

• 그리디, 정렬
  
  • 그리디 규칙을 잘 생각해보면 의외로 쉽게 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  결국 팀을 어떻게 정하는게 항상 최선의 선택일지 규칙을 정해야 한다.

얼핏 X값이 큰 학생들부터 골라서 선택해야 각 팀의 인원이 많아지므로 팀의 수가 줄어든다고 생각할 수 있는데, 어차피 X값은 고정된 것이고 바뀔 수 없으며, 모든 학생은 하나의 팀에 소속이 되어야만 한다.

 

  그렇다면 각 팀의 인원이 많아지는건 상관없고 필요한 규칙은 '최대한 많은 팀이 최대한 각 팀에서 가장 X값이 낮은 학생을 기준으로 가득 차있어야 한다.' 가 된다.

 

  그럼 이걸 어떻게 규칙화할지만 생각하면 되는데, 단순히 생각해보면 '각 팀에서 X값이 가장 낮은 학생'의 값이 갑자기 튀지만 않으면 된다. 최대한 근처 값끼리 묶어주면 된다. 예를들어 아래 케이스를 그냥 입력 들어온 그대로 차례대로 팀을 구해보면 '1 / 2 5 / 5 2 / 5 5' 이렇게 4개의 팀이 나온다.

7
1 2 5 5 2 5 5

 

  하지만 정렬 후 오름차순으로 팀을 구해보면 '1 / 2 2 / 5 5 5 5' 이렇게 3개의 팀으로 가능하다. 정렬이 최대한 X값이 가까운 학생들끼리 묶어주는 과정이 된다. 그리고 오름차순으로 순서대로 구해주면 되고, 혹은 내림차순으로 내려와도 상관없다. 즉 중요한건 정렬을 통해 X값의 차이를 최대한 줄여준 후 내림차순이던 오름차순이던 팀을 구해주면 된다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        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 answer = 0;
        int cnt = 0;
        int limit = 0;
        for (int i = 0; i < n; i++) {
            int cur = arr[i];
            if (cnt == 0) limit = cur;
            cnt++;

            if (cnt == limit) {
                cnt = 0;
                answer++;
            }
        }
        if (cnt != 0) answer++;

        System.out.println(answer);
    }
}