BOJ 2792 - 보석 상자

문제

---

보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.

한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.

상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.

상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.

 

---

이분 탐색을 활용하는 문제이다. 이분 탐색 중에서 파라메트릭 서치를 사용할 줄 알아야한다. 

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 푸는 것이라고 할 수 있다.

 

최적화 문제란 찾고자 하는 최적의 값을 찾는 것이라고 할 수 있겠다. 예를 들어 최솟값이나 최댓값, 조건을 만족하는 최적의 값을 찾는 것을 우리는 최적화 문제라고 부를 수 있다.

 

결정 문제

란 최적화 문제를 "yes" or "no" 둘 중 하나의 값으로 결정되는 문제를 말한다.

 

이 정의를 통해서 최적화 문제를 "yes" or "no"라는 두 가지 선택지를 찾아가며 이분 탐색을 적용한다. 즉 범위가 반씩 줄어들 것이다.

 

보석 상자 문제에서 최적화 문제는 무엇일까? 질투심이 최소가 되게 나누어주기 위해선 각 사람에게 최대한 공평하게 나눠줘야한다. 여기에서 최적화 문제는 보석을 최대한 공평하게 나눠주어 질투심의 최소값을 구하는 것이다.

 

즉 질투심을 기준으로 파라메트릭 서치하여 최대한 공평하게 나눠주는 최적의 점을 찾는 것이라고 이해했다.