문제링크
º https://www.acmicpc.net/problem/1654
사용 알고리즘
º 이분탐색
시간복잡도
º $\mathcal{O}(Nlog(2^{31}-1))$
풀이
k개의 랜선들을 일정한 크기로 잘라서 n개의 랜선으로 만들고 싶은데, 자르는 일정한 크기 중 최대의 크기를 구하는 문제입니다. 랜선의 길이의 범위가 $\mathcal2^{31}-1$ 까지 되서 시간문제 해결을 위해 이분탐색으로 탐색해준다.
탐색을 진행하며 랜선들을 나누어서 개수를 세어준 후 n개 이상이 되는지만 비교하면 되는 간단한 이분탐색입니다.
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <vector> using namespace std; int n, k,max_len; vector <int> v; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> k >> n; v.resize(k); for (int i = 0; i < k; i++) { cin >> v[i]; if (v[i] > max_len) max_len = v[i]; } long long ans=0,result,mid,left = 1, right = max_len; while (left <= right) { mid = (left + right) / 2; result = 0; // 현재 길이로 랜선을 나눴을때의 랜선 개수 for (int i = 0; i < k; i++) result += v[i] / mid; if (result >= n) // 랜선 개수가 n개 이상일때 성공 { left = mid + 1; if (mid > ans) ans = mid; } else right = mid - 1; } cout << ans; return 0; } Colored by Color Scripter |
cs |
'Algorithm > boj' 카테고리의 다른 글
백준 11651번 좌표 정렬하기 2 (0) | 2021.10.24 |
---|---|
백준 13397번 구간 나누기 2 (0) | 2021.10.24 |
백준 1939번 중량제한 (0) | 2021.10.24 |
백준 2805번 나무 자르기 (0) | 2021.10.24 |
백준 2110번 공유기 설치 (1) | 2021.10.24 |