[백준 12945] 재미있는 박스 정리 - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/12945

12945번: 재미있는 박스 정리

 

문제

민호는 N개의 박스를 가지고 있다. 어느 날 박스가 너무 많아져 박스를 정리하고 싶어졌다. 하지만 평범한 박스정리가 너무 지루하다고 생각한 민호는 재미를 위해 몇 가지 규칙을 정하고 박스를 정리하기로 생각했다. 규칙은 아래와 같다.

1. 박스 x의 크기를 V[x], 박스 y의 크기를 V[y]라 할 때 V[y]는 적어도 V[x]의 두배는 되어야지 x를 y에 넣을 수 있다.
2. 박스 x를 박스 y에 넣었다면 y는 다른 박스에 넣지 못한다. 한 박스안에 들어있는 모든 박스는 많아야 한 개이다.

위와 같은 규칙을 지켜 박스 정리를 할 때 최적의 경우를 구해보자. 최적의 경우라 하면 눈에 보이는 박스의 개수가 최소가 되는 경우를 의미한다.

 

입력

첫째 줄에 민호가 가지고 있는 박스의 개수 N (1 ≤ N ≤ 500,000) 이 주어진다.

두번 째 줄부터 N개의 줄에 걸쳐 민호가 가지고 있는 박스들의 크기 V (1 ≤ V ≤ 100,000) 이 주어진다.

 

출력

규칙을 지켜가며 박스 정리를 했을 때 최적의 경우를 출력한다.

풀이

접근법

1. 박스마다 최대 하나 넣을 수 있으니까 이걸 관리해줄 수 있는 배열이 필요할 것 같다.
2. 큰 박스에 큰 박스를 넣는 것부터 고려를 해야할 것 같다. 작은 박스에 작은박스부터 넣으면 3 6 8 12 와 같은 반례가 생긴다.
3. 박스는 최소 N/2가 나올 수 있으므로, s를 N/2-1로 시작하면 된다.
   1. 만약 s를 N-2, e를 N-1로 시작하게 되면 2 2 4 8 과 같은 반례가 생긴다.

 

코드

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

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];
        for(int i=0;i<N;i++) arr[i] = Integer.parseInt(br.readLine());
        // 1. 박스마다 최대 하나 넣을 수 있으니까 이걸 관리해줄 수 있는 배열이 필요할 것 같다.
        boolean[] checked = new boolean[N];
        Arrays.sort(arr);
        
        // 2. 큰 박스에 큰 박스를 넣는 것부터 고려를 해야할 것 같다. 
        // -> 박스는 최소 N/2가 나올 수 있으므로, s를 N/2-1로 시작하면 된다.
        int s = N/2-1;
        int e = N-1;
        while(s >= 0) {
            if (checked[e]) {
                e--;
                continue;
            }
            if (s >= e) {
                s = e-1;
            }
            while(s >= 0 && arr[s] * 2 > arr[e]) s--;
            if (s < 0) break;
            checked[s] = true;
            s--;
            e--;
        }
        int ans = 0;

        for(int i=0;i<N;i++) if (!checked[i]) ans++;
        System.out.println(ans);
    }
}

 

1시간 반 걸렸다.. 역시 MST와 같은 알고리즘 티어 높은 것보다 이런 그리디 알고리즘의 티어가 높은게 생각할 게 더 많은 것 같다.. 이렇게 오래걸린 문제가 오랜만인데 더 열심히 공부해야 겠다는 생각이 들었다.