[백준 - 12945번] 재미있는 박스 정리 - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: 그리디, 정렬

민호는 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) 이 주어진다.

출력

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

풀이

박스의 개수가 최소가 되어야 한다. 박스에는 최대 한 개만 담길 수 있다.

처음에 나는 가장 큰 박스에 담길 수 있는 박스 중 가장 큰 박스를 담는 방식으로 구현했다.
이 방식은 최선의 선택이 아니다. 다른 박스가 유일하게 담길 수 있는 박스를 담기 때문이다.

예를 들어 100 50 9 8 일 때 (100, 50), (9), (8)은 3이고, (100, 9), (50, 8)은 2다.

그러면 어떻게 풀어야 할까?

ex) 8, x1, x2, x3 이고, 8은 x1, x2, x3에 담길 수 있다고 했을 때 (x1 < x2 < x3)

1. x1에 담기면 (8, x1), (x2, x3)가 최선인데, x3가 x2를 못담을 수 있다. 그렇지만 x3가 x1을 담을 확률은 존재한다.

2. x3에 담기면 (8, x3), (x1, x2)가 최선인데, x1이 x2에 못담길 수 있다. 그렇지만 x3가 x2를 담을 확률은 존재한다.

3. x2에 담기면 (8, x2), (x1, x3)가 최선인데, x1이 x3에 못담길 수 있다. x1을 못담는다면 x2도 못담는다.

그래서 x2를 담는게 최선의 선택이라 할 수 있다.

여기서 내가 떠올랐던 생각은 8이 선택했을 때 x1이 박스에 담길 확률을 높이기 위해서는 가장 큰 x3를 남겨놔야 한다는 것이다.

이런 논리로 접근하면 6개일 때 8, x1, x2, x3, x4, x5

x2는 x5를, x1은 x4를 8은 x3가 된다.

이를 일반화하면
x1, x2, x3, x4

x1은 N/2 부터 N - 1 인덱스를 차례대로 탐색하면서 들어갈 수 있는 박스가 나오면, 그 박스에 넣어주고, < N/2 인덱스까지 반복해 준다.

x1에서 들어갈 수 없는 박스는 x2에서도 불가능하기 때문에 시간 복잡도는 O(N)으로 시간 초과없이 충분히 가능하다.

소스 코드

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

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] V = new int[N];
        for(int i=0; i<N; i++) {
            V[i] = Integer.parseInt(br.readLine());
        }
        
        System.out.println(answer(V));
    }
    
    static int answer(int[] V) {
        int cnt = 0;
        Arrays.sort(V);
        int start = V.length/2;
        for(int i=0; i<V.length/2; i++) {
            cnt += 1;
            while(start < V.length) {
                if(V[i] * 2 <= V[start]) {
                    start += 1;
                    break;
                }
                cnt += 1;
                start += 1;
            }
        }
        
        if(start != V.length) {
            cnt += 1;
        }
        return cnt;
    } 
}