[알고리즘] 백준 12945 : 재미있는 박스 정리 - JAVA

문제

---

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. x 박스를 y박스에 넣기 위해선 y 박스의 크기는 x * 2 이상이어야 한다. -> 큰 상자에 넣을 수 있는 제일 큰 상자 부터 넣기 (그리디)
2. 1개의 박스에는 최대 1개의 박스만 들어갈 수 있다. -> 상자가 모두 짝수개 이면 최소 N / 2, 홀수인 경우 최소 N / 2 + 1개

위의 두 조건에 따라서 구현하였습니다.

우선 1번의 조건을 만족하기 위해 먼저 박스를 담은 배열을 정렬 후에 제일 큰 상자가 들어 있는 배열의 끝과 최소개의 상자가 될 수 있는 중간 지점부터 검사하여 문제를 풀이 할 수 있었습니다.

 

 

코드

---

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 NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 박스의 개수
		
		int[] boxArr = new int[N]; // 박스 배열
		for(int i = 0; i < N; i++) {
			boxArr[i] = Integer.parseInt(br.readLine()); // 박스 크기 입력
		}
		
		Arrays.sort(boxArr); // 박스 정렬
		int inBox = 0; // 담을 수 있는 박스의 수
		for(int i = N/2 - 1, j = N - 1; i >= 0; i--) { // i = 정리후 최소개가 될 수 있는 박스의 수 이하부터 검사, j = 최대 크기의 박스 부터 검사
			if(boxArr[i] * 2 <= boxArr[j]) { // 담을 수 있다면 cnt
				inBox++;
				j--;
			}
		}
		System.out.println(N - inBox); // 총 박스의 수 - 담을 수 있는 박스의 수
	}
}