[알고리즘] 백준 | 15810 풍선 공장

풍선 공장

이분탐색 문제

답: 

from sys import stdin

input = stdin.readline
N, M = map(int, input().split()) #인원, 갯수
time = list(map(int, input().split()))

start = 0
end = max(time) * M + 1

while start <= end:
    mid = (start + end) // 2
    balloon = 0

    for t in time:
        balloon += mid // t

    if balloon >= M:
        end = mid - 1
        result = mid # 무조건 큰거에다가 넣어야한다 = 결과가 M이상이므로
    else: # balloon < M
        start = mid + 1

print(result)

 

 

문제 분석 및 해석

풍선을 담당하는 N명의 스태프 풍선만드는 속도는 다르다

M개의 풍선을 만들어 달라는 의뢰.

각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

 

입력 :

3 8  # N, M

5 7 3 # 각 스태프가 풍선 만드는데 걸리는 시간

출력 :

14

 

입력 :

3 8

1 1 1

 

출력 : 

2

 

 

 

>> 풀이생각

이진탐색을 이용해서 풀이한다.

while 문 / 재귀함수 모두로 풀이해보자.

 

 

 

리뷰.

 

처음엔 ==으로 풀이했는데, 이 문제의 경우 M이상 인 결과가 도출되므로

==이 아닌 변수에 저장하고 while문이 종료되면 return해주는 식으로 풀이해야한다.

 

if balloon == M:
    # 여기서 완벽히 일치하지 않는 경우를 걸러내지 못한다
    print(mid)
    break

 

 

또한  mid값을 balloon변수값이 크다 == target값이 > 작다 표시되어있는 쪽에 저장해주어야  한다

M 이상의 값이므로!!

 

if balloon >= M:
    end = mid - 1
    result = mid ## =은 target이 작다 > 는 쪽에 넣어야 함!! 
else:
    start = mid + 1

 

 

+++ 

binary_search 재귀 함수로 구현하기