본문 바로가기

이분 탐색3

[BOJ] 백준 1654번: 랜선 자르기, 이분 탐색 (Binary Search) www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이 문제는 주어진 랜선 K개의 길이를 잘라 같은 길이의 N개를 만들 때 최대 랜선의 길이를 구하는 문제입니다. 랜선의 길이가 INT_MAX 값보다 작거나 같은 자연수 이므로 Naive한 방법으로는 시간초과가 발생하므로 해결할 수 없습니다. 자를 수 있는 랜선 길이의 범위 내에서 가능한 최대 길이를 구하는 문제로 정렬된 순열에서 특정 값을 찾는 문제로 해석할 수 있고 이는 이분 탐색을.. 2020. 9. 7.
[BOJ] 백준 1024번: 수열의 합 https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net L 이상 100이하 길이의 연속된 수로 구성된 수열의 합이 N을 구하는 문제입니다. 도저히 풀이가 떠오르지 않아 모든 L에 대하여 이분탐색으로 가능한 경우의 수를 탐색했습니다. #include #include #include using namespace std; typedef long long ll; ll n, l; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(.. 2020. 8. 12.
[BOJ] 백준 13537번: 수열과 쿼리 1 머지 소트 트리 + 이분탐색 아래글 참고. 2020/08/17 - [알고리즘] - 머지 소트, 머지 소트 트리 및 관련 백준 문제 풀이 #include #include #include #include #include #include using namespace std; typedef long long ll; int n, m, k; int arr[100001]; int mst[17][100002] = { 0, }; void make_tree(int s, int e,int depth) { if (s == e) { mst[depth][s] = arr[s]; } else { int mid = (s + e) / 2; make_tree(s, mid, depth + 1); make_tree(mid + 1, e, de.. 2020. 6. 22.

티스토리툴바