반응형 파라매트릭서치3 백준 3079번 입국심사 - C++ 풀이 1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다. 2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다. 1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다. t초동안 심사할 수 있는 사람 수를 최대로 하려면, 각 심사대가 쉬지 않고 일을 해야 한다. 따라서 각 심사대가 t / Tk명을 처리할 수 있고 이를 모두 더하면 t초 동안 심사할 수 있는 사람의 수의 최댓값을 구할 수 있다. 시간복잡도는 O(N). 2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다. M명을 모두 처리할 수 있는 최소 시간을 min_t라고 하면, t >= min_t인 경우 항상 모든 사람 심사가 가능하고 t < min_t인 경우 항상.. 2023. 8. 5. 백준 1561번 놀이 공원 - C++ 풀이 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 시간이 주어지면 해당 시간까지 각 놀이기구가 몇 번 운행되는지 구할 수 있다. 따라서 먼저 모든 사람이 놀이기구에 탑승하는 데 걸리는 시간 totalTime을 찾아주자. 파라매트릭 서치를 이용하여 O(log30N)에 totalTime을 구할 수 있다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 현재 시각을 t라고 하면, 마지막 놀이기구는 t = totalT.. 2022. 7. 21. 백준 1981번 배열에서 이동 - C++ 풀이 1. 파라매트릭 서치를 이용하여 가장 작은 gap을 찾는다. 2. maxVal - minVal = gap이 되는 모든 (minVal, maxVal) 쌍에 대하여, (1,1)에서 출발하여 minVal 이상 maxVal 이하인 칸들로만 (n, n)에 도착할 수 있는지 여부를 DFS/BFS를 사용하여 구한다. 1. 파라매트릭 서치를 이용하여 가장 작은 gap을 찾는다. (최대-최소) = gap이라 하자. 가장 작은 gap을 구하는 최적화 문제이다. 이를 결정문제로 바꾸어 줄 것이다. decision(gap)을 최대값과 최소값의 차가 gap 이하가 되도록 할 수 있는가로 정의하고, 이분탐색을 이용하여 최초로 가능한 gap을 찾는다. 2. maxVal - minVal = gap이 되는 모든 (minVal, max.. 2022. 7. 4. 이전 1 다음 반응형
