반응형 이분탐색4 백준 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. 백준 3020번 개똥벌레 - C++ 풀이 1. 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 1. 종유석과 석순을 따로 저장한다. 두 장애물의 방향이 다르므로 종유석과 석순을 따로 저장한다. 2. 이분 탐색을 이용해서 높이 h로 날 때 파괴해야 하는 종유석과 석순의 개수를 구한다. 종유석은 끝부분이 h 미만인 것들을 파괴해야 하고, 석순은 끝부분이 h 초과인 것들을 파괴해야 한다. 따라서 종유석과 석순을 각각 정렬한 뒤, 이분 탐색을 이용하여 파괴해야 하는 개수를 각각 구해주면 된다. 3. 모든 구간에 대해 파괴해야 하는 장애물의 개수를 구한 뒤 최솟값을 찾는다. 총 H개의 구간에 대해 파.. 2022. 8. 27. 백준 1561번 놀이 공원 - C++ 풀이 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 1. 파라매트릭 서치를 사용하여 모든 사람이 놀이기구에 탑승하기 위해 필요한 최소 시간 totalTime을 구한다. 시간이 주어지면 해당 시간까지 각 놀이기구가 몇 번 운행되는지 구할 수 있다. 따라서 먼저 모든 사람이 놀이기구에 탑승하는 데 걸리는 시간 totalTime을 찾아주자. 파라매트릭 서치를 이용하여 O(log30N)에 totalTime을 구할 수 있다. 2. totalTime을 이용해서 마지막 사람이 탑승하는 놀이기구 번호를 구한다. 현재 시각을 t라고 하면, 마지막 놀이기구는 t = totalT.. 2022. 7. 21. 백준 1450번 냅색문제 - C++ 풀이 1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다. 2. A그룹에서 무게 w를 만들 수 있다면, B그룹에서 무게 C-w 이하를 만들 수 있어야 한다. 3. A그룹에서 만들 수 있는 모든 무게에 대해, 이분 탐색을 이용하여 B그룹에서 C-w이하를 만드는 조합의 수를 구한다. 1. 전체 물건을 두 그룹으로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해둔다. 모든 조합의 수는 2^N, N=30이므로 브루트 포스로는 제한시간 내에 통과할 수 없다. 이런 경우 두 그룹으로 쪼개 조합의 가짓수를 줄이는 방법을 사용할 수 있다. 두 그룹 A, B로 나눈 뒤, 각 그룹에서 가능한 모든 조합을 탐색하여 기록해두자. 이 과정의 시간복잡도는 O(2^N/2). 2. A그.. 2022. 7. 1. 이전 1 다음 반응형
