백준 - 도도의 음식 준비 - 22953 - swift

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

22953번: 도도의 음식 준비

 

 

문제는 완전탐색과 이분탐색으로 볼 수 있다.

완전탐색에는 순열과 조합을 이용했다. 

 

크게 문제는 최적의 시간을 찾는 것으로, 

각 요리사들에는 요리 시간이 정해져있고, K개의 음식을 모두 준비하는데 걸리는 가장 빠른 시간을 찾는 문제다.

이러한 유형은 미리 최적의 시간이 X라고 정하고서 탐색하는 방법, 즉 이분 탐색으로 푼다.  

( 왜냐하면, 이분 탐색없이 고민한다면 완전탐색으로는 시간 초과가 날 수 밖에 없다. ) 

 

하지만 문제는 그렇게 간단한게 아닌데, 다른 키포인트는 격려해줄 수 있는 횟수다.  

언뜻 보면 가장 낮은 요리사에게 격려해주면 되지 않을까? 생각이 들지만, 

( 대체로 확신이 없다면 내 생각이 틀리더라 )

우선 예제 2, 3 번을 보면 무조건 요리시간이 낮은 요리사에게 격려를 해준다고 해서 최적의 시간이 나오지 않는다는 점이다. 

 

그리고 눈에 띄는 점이 격려 횟수가 최대 5밖에 되지 않는다. 

그리고 요리사 수도 최대 10밖에 되지 않는다. 

 

그러므로 이분탐색을 결정하기 전에, 우선 요리사들에게 미리 격려를 해준다음에, 이분탐색을 시행해야한다.

또 위의 요소들을 종합해보면, 요리사들에게 격려를 해줄 수 있는 모든 경우의 수를 구하는 것이다. 

 

요리사가 10명이고, 최대 격려횟수가 5라면,  최소 1명~최대 5명까지 격려해줄 수 있다. 

격려의 경우의 수는 

1,1,1,1,1

1,1,1,2 

1,1,3

1,4

5

2,2,1

2,3

.... 

 

이렇게 다양하게 나오고,

이제 나온 격려의 경우의 수를 통해서, 어떤 요리사에게 배정할지도 찾아야한다.

즉, 2,2,1 의 격려의 경우에는  10C3을 통해서 요리사의 배정을 찾는다.

 

즉, 격려의 경우의 수를 순열로 찾아내고,

찾아낸 바탕으로, 요리사의 배정을 조합으로 찾아냈다.

그리고 각각의 결과로, 요리사들의 시간을 줄인다음, 이분 탐색을 시행한다.

 

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

func find(_ l: [Int], _ value: [Int]) {
    var list = list
    zip(l,value).forEach {
        list[$0] = max(1, list[$0]-$1)
    }
    var l = 1, r = 1_000_000_000_000
    while l<=r {
        let mid = (l+r)/2
        var sum = 0
        list.forEach {
            sum += mid/$0
        }
        if sum >= K {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    ans = min(ans, l)
}

func combi(_ idx: Int, _ l: [Int], _ value: [Int]) {
    if l.count == value.count {
        find(l, value)
        return
    }
    for i in idx..<N {
        combi(i+1, l+[i], value)
    }
}

func permu(_ l: [Int], _ sum: Int ) {
    if sum == C {
        combi(0, [], l)
        return
    } else if sum > C {
        return
    } else {
        for i in 1...C {
            permu(l+[i], sum+i)
        }
    }
}

permu([], 0)
print(ans)