백준 1561 - 놀이공원 - swift

 

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

1561번: 놀이 공원

 

 

꽤나 정답비율이 낮은 편에 속하는 문제다.

 

이렇게 낮은문제는 한번에 떠오르는 생각만으로 접근하다보면은 틀리기 십상이다.

그러므로 예외처리나, 더 세세하게 경우들을 생각하거나, 구현을 잘해야한다. 

 

 

일단 N이 20억으로, 한명한명 모두 태워보며 마지막을 찾기란 시간초과다.

 

그러므로 시간안에 풀수있는 효율적인 방법이 필요하다.

 

"시간"을 기준으로 문제를 접근해본다. 

총 M개(최대 만개)의 놀이기구가 있고, N명의 대기자가 있다.

이를 "X분"에 N명의 대기자가 모두 탈수있는가? 로 접근하는 거다.

각 놀이기구의 대기시간을 X로 나눈값 + 1 이, 해당 놀이기구의 태울수있는 대기자수다.

 

그러므로,  0분부터, 운행시간은최대 30분이랬으므로, 최악의경우 M이 1개이면서 N이 20억이므로, 최대 600억사이의 값을

이분탐색하여 X분을 찾아낸다.

600억은 Log2로하면 40도 채안되므로, 40번안에 빠르게 찾을 수 있다. 

 

여기까지는 무난한 문제지만, 이제 그후, 가장 중요한,  마지막대기자가 몇번 놀이기구에 탈수있는지이다.

 

이미 이분탐색에서 종료조건이,  항상 N보다 크거나 같은경우의 시간일경우이므로, 

찾은 X를 , X-1로 하게되면 N보다 작은 인원이 나올수밖에없다.

그러므로, X-1로, 탈수있는 인원들을 미리 걸러둔다.  

그다음에, X분에 태울수있는 놀이기구들만 차례대로 확인하면 된다. 

 

let inp = readLine()!.split(separator: " " ).map{Int(String($0))!}
let N = inp[0], M = inp[1]
let times = readLine()!.split(separator: " " ).map{Int(String($0))!}

var l = 0, r = 60_000_000_000
var s = 0
while l<=r {
    let mid = (l+r)/2
    s = 0
    times.forEach{
        s += mid/$0 + 1
    }
    if s >= N {
        r = mid-1
    } else {
        l = mid+1
    }
}

s = 0
if l != 0 {
    times.forEach{
        s += (l-1)/$0 + 1
    }
}

for i in 0..<M {
    
    if l%times[i] == 0 {
        s += 1
    }
    
    if s == N {
        print(i+1)
        break
    }
}