https://www.acmicpc.net/problem/2792
2792번: 보석 상자
보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하
www.acmicpc.net
📌 해결과정
우선 문제를 읽고 문제를 풀기위해 필요한 조건들을 정리했다.
학생들의 질투심을 최소화 한다 = 한 학생이 갖는 같은 색상의 보석의 갯수를 최소화 한다
1. 모든 보석을 남김없이 학생들에게 나누어 줘야한다.
2. 한 학생은 같은 색상의 보석만 가질 수 있다.
3. 보석을 갖지 못하는 학생이 있을 수 있다.
어떻게 풀어야 할지 감을 잡지 못하다가 두번 째 예시를 통해서 힌트를 얻고 풀었다.
이렇게, 예제 2를 통해서 몫과 나머지를 이용해야 하는 방법을 찾았다.
만약 검은색 보석이 7개가 있고 질투심이 3이라면 3 3 1 로 나누어서 학생에게 줘야하고,
각 학생은 같은 색상의 보석만 가질 수 있으므로 3명의 학생에게 나누어 줘야 한다.
남기는 보석이 없어야 하므로 무조건 3명을 써야한다.
🧐 이분 탐색
질투심 A 로 나누어준 학생의 수가 실제 학생 수 보다 많다 = 질투심이 작다.
따라서 A 질투심 보다 작은 경우에 대해서 탐색 할 필요가 없다.
질투심 A 로 나누어준 학생의 수가 실제 학생 수 보다 적다 = 질투심이 크다
따라서 A 질투심 보다 큰 경우에 대해서 탐색 할 필요가 없다.
질투심의 최솟값을 찾아야 하므로 질투심이 큰 값부터 줄여 나가야 했다.
start = 1 이다. 만약 0 이면 mid 값이 0 이 되는 경우가 생긴다 따라서 값이 무한으로 발산 하므로 런타임 에러가 발생한다.
end 는 보석 색상 중에서 가장 갯수가 많은 보석이다.
📌 코드
import sys
input = sys.stdin.readline
students, jewel_type = map(int, input().split())
colors = [int(input()) for _ in range(jewel_type)]
colors.sort()
start = 1
end = colors[-1]
ans = 0
while start <= end:
tmp_students = 0
mid = (start + end) // 2
for color in colors:
if color % mid == 0:
tmp_students += color // mid
else:
tmp_students += color // mid + 1
if tmp_students <= students:
end = mid - 1
ans = mid
else:
start = mid + 1
print(ans)
'algorithm > Binary Search' 카테고리의 다른 글
백준 6236 용돈 관리 (0) | 2022.09.22 |
---|---|
백준 3079 입국심사 (0) | 2022.09.22 |
백준 2805 나무 자르기 (0) | 2022.09.22 |
백준 1654 랜선 자르기 (0) | 2022.09.22 |
백준 1920 수 찾기 (0) | 2022.09.22 |