이진 탐색
-
[백준] 2805번 나무 자르기알고리즘/백준 2021. 8. 29. 16:49
문제 링크 풀이 내가 가져갈 수 있는 나무 길이가 나오는, 나무의 절단 높이를 구하는 문제다. 20 높이의 나무의 15로 높이로 절단하면 5를 가져간다. 이 문제의 특성은 이분 탐색을 통해 절단 높이를 구해가는 과정에서, 절단 높이가 작아질수록 잘린 나무의 길이가 커지는 데 있다. 그러므로 일반적인 이분 탐색에서 high, low를 구하는 조건을 반대로 해주면 된다. 코드 #include #include using namespace std; // 2805번 int main() { int N; // 나무 수 scanf("%d", &N); vector trees(N); long long M; // 필요한 나무의 길이 long long answer = 0; // 절단기에 설정할 최대 높이 long long h..
-
[백준] 3079번 입국 심사알고리즘/백준 2021. 8. 27. 18:44
문제 링크 프로그래머스 풀이 심사대의 범위가 1 ~ 100,000이고 친구들의 숫자가 최대 10억명이므로 이분 탐색을 사용하지 않으면 시간이 너무 오래 걸리게 될 겁니다. 이 문제에서는 어디에 이분 탐색을 사용해야 할까요. 우리가 구하고자 하는 답은 주어진 인원이 입국 심사 하는 데 걸리는 최소 값입니다. 입국 시간과 인원과의 상관 관계를 먼저 생각해볼게요. 예제에서 두 개의 심사대가 주어지고 각각 심사 시간이 7분, 10분입니다. 만약 입국자에게 5분이 주어진다면 어느 누구도 심사대를 통과할 수 없을 겁니다. 7분이면 1명만 통과할 수 있고요 10분은 돼야 2명이 받을 수 있습니다. 직관적으로 계산할 수 있지만 수식으로 해보면, 주어진 시간이 X일 때 각 심사대의 심사 시간을 나눈 값을 더한 총합입니다..