https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
www.acmicpc.net
parametric search를 이용해서 푸는 문제이다. parametric search는 답이 나올 수 있는 범위 안에서 이분 탐색을 통해 답을 구하는 방법이다.
이 문제에서 가장 작게 자르는 크기는 1이고, 가장 크게 자르는 경우는 랜선의 길이중 최대값이기 때문에 각각 left값과 right값이 된다.
mid값으로 자르는 경우마다 잘라지는 랜선의 개수를 구하고
그 개수가 n값 이상인 경우에는 size를 더 늘릴 수 있으므로 left를 mid +1로 옮겨준다.
반대로 n값 보다 작은 경우에는 현재 mid값으로 n개를 만들 수 없으므로 right를 mid -1 로 옮긴다.
이 문제에서 주의할 점은 랜선의 길이가 2의31승 -1보다 작은 값이므로 left와 right를 더했을때 int범위를 넘어갈 수 있기때문에 타입을 long long으로 해줘야한다.
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <algorithm>
using namespace std;
int k, n;
int arr[10000];
long long getCount(long long size) {
long long cnt = 0;
//k개의 랜선을 size(mid)로 잘라서 나오는 개수를 더해준다.
for (int i = 0; i < k; i++) {
cnt += (arr[i] / size);
}
return cnt;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> k >> n;
for (int i = 0; i < k; i++) cin >> arr[i];
//입력 받은 랜선길이를 정렬한다.
sort(arr, arr + k);
int ans;
//자를 수 있는 가장 작은 단위인 1이 left값
long long left = 1;
//자를 수 있는 가장 큰 단위(최댓값)인 arr의 마지막 값이 right
long long right = arr[k - 1];
//이분 탐색
while (left <= right) {
long long mid = (left + right) / 2;
//mid값으로 잘랐을때 나오는 랜선의 개수를 구한다
long long cnt = getCount(mid);
//mid값으로 잘라서 나온 랜선의 개수가 n이상이면 더 큰 값으로 잘라도 되므로 left값이 앞으로 간다.
//현재 최대 길이는 mid값 만큼 자른 경우
if (cnt >= n) {
left = mid + 1;
ans = mid;
}
else {
//현재 mid값으로 랜선을 자르면 n개를 못만드는 경우
//크기르 줄이기 위해 right를 mid앞쪽으로 당긴다.
right = mid - 1;
}
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2167. 2차원 배열의 합 (0) | 2020.01.24 |
|---|---|
| [BOJ] 2805. 나무 자르기 (0) | 2020.01.21 |
| [BOJ] 10816. 숫자 카드 2 (0) | 2020.01.20 |
| [BOJ] 5567. 결혼식 (0) | 2019.11.13 |
| [BOJ] 7662. 이중 우선순위 큐 (0) | 2019.11.13 |