반응형 binarySearch3 BOJ 1654 - 랜선 자르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 이미 갖고 있는 랜선들 k개를 잘라 n개의 랜선을 만들 때, 랜선 하나의 최대 길이를 구하면 된다. 그러기 위해서는 랜선의 길이를 x라 했을 때, 원소들에 대해 (LANlines[i] / x)를 구하여 몇 개의 랜선을 만들 수 있는지 구한 뒤 모두 더해 n개 이상 만들 수 있다면 정답이 될 수 있다. 따라서 0부터 랜선의 최대 길이를 이분 탐색.. 2022. 3. 4. BOJ 2805 - 나무 자르기 / C++ 문제 링크 : https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 나무들의 높이가 주어지고 절단기의 길이가 x일 때 (trees[i] - x)만큼 집에 나무를 가져갈 수 있다. 적어도 m미터의 나무를 가져가기 위한 절단기의 최대 길이를 구하면 된다. 이를 구하기 위해 이분 탐색을 이용한다. 일반적인 이분 탐색은 원소 값들을 탐색하지만 해당 문제에서는 원소 값들을 탐색해서는 답을 찾을 수 없다. 따라.. 2022. 3. 4. BOJ 1920 수 찾기 / C++, 시간 초과 방지 팁 문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 첫 번째 배열에 두 번째 배열 값들이 존재하는지 찾는 문제이다. 이진 탐색을 사용하기 위해 첫 번째 배열들은 정렬을 해준다. 두 번째 배열들은 입력받자마자 이진 탐색을 통해 해당 값들이 첫 번째 배열에 있는지 확인한다. C++에서 시간 초과를 방지하려면 (1) ios_base::sync_with_stdio(false); ci.. 2021. 9. 1. 이전 1 다음 반응형