백준 15732 - 도토리 숨기기 - swift

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

15732번: 도토리 숨기기

 

조금 고민이 필요한 문제였다. 

하나씩 규칙들을 탐색하면서 각 상자에 카운팅해도되겠지만, 1개씩 찾다보면 도토리가 총 10억개이므로 시간초과다. 

좀 더 효율적으로 찾는 방법이 필요하다. 

 

고민을해보니,  100~150개에서, 10간격이라면, 총 6개 도토리를 넣을수있다.

110~150, 15간격이라면 총 3개 도토리를 넣을 수 있다.

그럼, 100 ~ x개에서 10간격이라면 총 몇개를 넣을 수 있을까? 

(x-100)/10 + 1 도토리를 넣을수있다. 

 

즉, 1부터 N개까지에서 이분탐색으로 mid를 찾는다.

이 mid가 위에서말한 x가 된다.

즉 각 규칙들의 첫번째값과 min( mid, 두번째값)에서, 간격/세번째값 +  1 이 해당규칙에서 얻을수있는 도토리개수가된다.

그러므로, 모든규칙들에 대해서 mid까지로부터 얻을수있는 총 도토리개수가 D보다 크거나같은경우는 

mid를 줄여본다. 

 

조금더 빠르게하기위해 규칙들을 정렬하고 시작할 수 있다.

 

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

var list = [(Int,Int,Int)]()
for _ in 0..<K {
    let q = readLine()!.split(separator: " ").map{Int(String($0))!}
    list.append((q[0],q[1],q[2]))
}

list.sort{$0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0}

var l = 1, r = N

while l<=r {
    let mid = (l+r)/2
    var sum = 0
    for i in 0..<K {
        let t = list[i]
        if t.0 > mid || sum >= D { break }
        sum += ((min(t.1, mid) - t.0)/t.2 + 1)
    }
    if sum>=D {
        r = mid-1
    } else {
        l = mid+1
    }
}

print(l)