[백준] 2792 Python | 15810 Python : 이분탐색법

이분탐색법을 이용해 최소/최대 값으로 답이 결정되는 알고리즘을 풀어보자

---

2792 번

문제

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

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

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

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

입력

첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 109, 1 ≤ M ≤ 300,000, M ≤ N)

다음 M개 줄에는 구간 [1, 109]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.

출력

첫째 줄에 질투심의 최솟값을 출력한다.

 

예제1

[입력]     [출력]
5 2       3
7
4

 

예제2

[입력]    [출력]
7 5       4
7
1
7
4
4

---

이분탐색법은 주어진 정답 구간의 최소값과 최대값을 각각 left point, right point로 잡고, 그의 중간값을 확인하여 답에 맞는지 확인하며 찾아가는 방법이다. 기준이 되는 lt, rt의 중간값으로 왼쪽구간, 오른쪽 구간을 나누기 때문이 이분탐색이라고 한다.

 

위 문제에서 정답으로 요구하는것은 "질투수치" 이다. 질투수치는 보석을 나눠받은 학생들 중 최고로 많은 보석을 가져간 학생의 보석갯수를 의미한다. 이 값의 최소치를 구한다는 것은 곧, 학생들에게 보석을 최대한 적게 골고루 나누준다는 뜻이다.

 

위 문제에서 주어진 조건은

1. 학생은 한가지 색의 보석만 받을 수 있다.

2. 보석은 모두 나눠주어야 한다. (보석이 남으면 안됨) 그러나 보석을 아예 못받는 학생이 있을 수 있다. (5명중 3명만 보석받아도 괜찮음)

 

위 두가지 조건에 유의하며 코드를 작성해 보았다.

import sys
sys.stdin = open("input.txt")

students, color = map(int, input().split())
jewels = [int(input()) for _ in range(color)]

lt = 1  # 보석을 나눠받는 가장 작은 수 1
rt = max(jewels) # 보석을 나눠받는 가장 큰 수
while lt <= rt:
    mid = (lt + rt) // 2  # 중간값 탐색
    get_s = 0  # mid 갯수로 보석을 나눠받은 총 학생 수
    for j in jewels:
        if j % mid == 0:
            get_s += (j//mid) # 똑 나눠 떨어지면 몫이 곧 그 수만큼 나눠받은 학생 수
        else:
            get_s += (j//mid) + 1 # 안나눠떨어지면 몫에다가 나머지만큼 가져간 학생 수
            
    if get_s > students:
    	# 나눠받은 학생 수 가 주어진 학생수보다 많다면 더 많이씩 나눠줘야 한다.
        lt = mid + 1
    else:
        # 나눠받은 학생 수가 주어진 학생수보다 같거나 적다면 더 적게 나눠줘도 된다.
        rt = mid - 1
print(lt)  #

 

[변수] mid, get_s

- 이분탐색을 진행하면서 몇개의 보석으로 학생들이 나눠받을 것인지 mid 값을 정한다. 이 값은 항상 구간의 최소값과 최대값의 중간값이다. (2로 나눈 몫)

- mid 갯수만큼 보석을 나눠받을때, 한개 색상의 보석이 mid의 배수이면 그 몫 만큼의 학생수가 보석을 나눠갖는다.

- mid 갯수만큼 보석을 나눠받을때, 한개 색상 보석의 수가 mid로 나누었을때 나머지가 발생한다면 몫의 수 만큼의 학생이 mid값 만큼의 보석수를 나눠갖고, 한 학생은 나머지 수 만큼 보석을 나눠받게 되므로 몫 + 1 만큼의 학생들이 나눠받게 된다.

 

[계산하기] lt, rt

> lt = mid + 1

mid 갯수만큼 학생들이 보석을 나눠가질때, 나눠갖게된 학생의 수가 문제로 주어진 students의 수보다 크다면 이는 보석을 좀더 많이씩 나눠가져서 나눠받는 학생의 수를 줄여하 한다는 것을 의미한다.

따라서 mid 갯수만큼은 정답이 되지 않는것을 인지하고, 탐색 범위를 높이기 위해 최소값이었던 lt를 mid+1만큼으로 변경한다.

 

> rt = mid - 1

mid 갯수만큼 학생들이 보석을 나눠가질때, 나눠받은 학생의 수가 주어진 students의 수보다 같거나 적다면 일단 mid값은 정답이 된다는 것이다. 하지만 답에서 구하는것은 그 값의 최소값이기 때문에 더 작은 값도 정답이 될수 있는지 탐색해야 한다.

따라서 mid 값보다 1 작은수로 rt값을 변경하고 그 사이값들을 비교한다.

 

[정답 도출하기] lt

while 문을 빠져나오는 조건은 두가지가 있다.

1. lt와 rt의 값이 동일할때, lt 값이 mid+1 된 경우

2. lt와 rt의 값이 동일할때, rt 값이 mid-1 된 경우

 

먼저 1번의 경우 새로운 lt값이 된 mid+1값은 언젠가 그 값이 정답이었던 mid 값이다. 따라서 while 조건에서 벗어나게 되어 더이상 탐색이 불가능하게 되더라도 lt값은 이전에 정답으로 체크되었던 mid 값이었으므로 정답이 된다.

 

2번의 경우 이미 2번의 조건이 정답에 부합하는 조건이므로 그 당시의 lt값 (이때는 lt와 rt가 같지만 한번 더 탐색을 위해 rt값이 줄어들어버린것) 을 정답으로 확정한다.

 

---

주어진 예제 1번을 확인해보면 [정답 도출하기]의 2번 상태에서 while 문이 종료된다. 예제2번의 경우 1번 상태에서 while 문이 종료되는데 풀이를 확인해보면 아래와 같다.

 

 

---

15810번

위와 동일한 개념으로 문제를 풀면 된다.

import sys
sys.stdin = open("input.txt")

staff, ba = map(int, input().split())
times = list(map(int, input().split()))

lt = 1
rt = max(times) * ba

while lt <= rt:
    mid = (lt + rt) // 2
    # 총 소요시간이 mid일때 몇개까지 풍선을 불 수 있는가
    total_balloon = 0
    for one in times:
        # 불고나서 몇분 남았다 해도 그 시간안에 부는것 완성 못하므로 나머지는 버린다.
        total_balloon += mid//one
    if total_balloon >= ba:
        # 목표갯수와 같거나 보다 많다면 총 소요시간을 줄여본다
        rt = mid - 1
    else:
        # 목표갯수보다 모자르다면 총 소요시간을 늘려준다
        lt = mid + 1
print(lt)

 

최소 / 최대 값이 답으로 결정되는 알고리즘 풀이법에는 이렇게 이분탐색법을 활용할수 있으므로 이 개념을 꼭 익혀두면 좋다!