문제링크

  º  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

+ Recent posts