[Swift 알고리즘] 백준_15810 (풍선 공장)

문제

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.

풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.

대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!

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

풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.

모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.

입력

스태프의 수 N과 풍선의 개수 M이 입력된다. (1 ≤ N, M ≤ 1 000 000)

다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai가 순서대로 주어진다. Ai는 1 000 000 이하의 자연수이다.

출력

M개의 풍선이 다 만들어지는 최소 시간을 출력한다.

예제 입력 1 

3 8
5 7 3

예제 출력 1 

14

힌트

1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 1번 스태프가 1개를, 12분에 3번 스태프가 1개를, 14분에 2번 스태프가 마지막 1개를 만들면 총 14분으로 최소 시간이 걸린다. 

 

https://www.acmicpc.net/problem/15810

15810번: 풍선 공장

 

 

 

풀이 방법 :

이분 탐색- 이분 탐색을 통해 풍선의 최솟값을 구하면 되었습니다. 이분탐색을 풀 때 마다 헷갈리는 while의 조건인 "start < end" 는 "start <= end" , 그리고 end = mid, end = mid + 1 등 조건이 헷갈렸던 문제였습니다. 풀이방법을 보니 각자 조건에 따른 쓰는 코드가 있었던 것을 확인할 수 있었습니다.

 

 

전체코드 

import Foundation

func sol() {
    let NM = readLine()!.split(separator: " ").map{Int($0)!}
    let (N, M) = (NM[0], NM[1])
    let staffs = readLine()!.split(separator: " ").map{Int($0)!}

    var start = 1
    var end = staffs.min()! * M
    while start < end {
        let mid = (start + end) / 2
        let tempSum = staffs.map{mid / $0}.reduce(0){$0 + $1}
        if tempSum >= M {
            end = mid
        }else {
            start = mid + 1
        }
    }
    print(end)
}
sol()