문제
정래는 김밥가게 “그르다 김가놈”에 납품할 김밥을 만드는 김밥 공장을 운영한다. 정래는 김밥 양쪽 끝을 “꼬다리”라고 부른다. 그리고 꼬다리를 잘라낸 김밥을 “손질된 김밥”이라고 부른다.
공장에서는 김밥 N개에 대해서, 김밥 꼬다리를 잘라내고 손질된 김밥을 김밥조각으로 만드는 작업을 한다. 꼬다리를 잘라낼 때에는 양쪽에서 균일하게 K cm만큼 잘라낸다. 만약 김밥의 길이가 2K cm보다 짧아서 한쪽밖에 자르지 못한다면, 한쪽만 꼬다리를 잘라낸다. 김밥 길이가 K cm이거나 그보다 짧으면 그 김밥은 폐기한다.
손질된 김밥들은 모두 일정한 길이 P로 잘라서 P cm의 김밥조각들로 만든다. P는 양의 정수여야 한다. 정래는 일정한 길이 P cm로 자른 김밥조각을 최소 M개 만들고 싶다. P를 최대한 길게 하고 싶을 때, P는 얼마로 설정해야 하는지 구하시오.
입력
첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수)
두 번째 줄부터 김밥의 길이 L이 N개 주어진다. (1 ≤ L ≤ 109, L은 정수)
출력
김밥조각의 길이 P를 최대로 할 때, P를 출력한다. 만족하는 P가 없는 경우, -1을 출력한다.
|
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<int> gimbap;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, m, gb;
int l = 1, r = 1000000000, mid, count, p = -1;
cin >> n >> k >> m;
for (int i = 0; i < n; i++) {
cin >> gb;
if (gb > 2 * k)
gimbap.push_back(gb - 2 * k);
if (2 * k > gb && gb > k)
gimbap.push_back(gb - k);
}
while (l <= r) {
mid = (l + r) / 2;
count = 0;
for (int gb:gimbap)
count += gb / mid;
if (count >= m) {
p = mid;
l = mid + 1;
} else
r = mid - 1;
}
cout << p << '\n';
return 0;
}
|
cs |
간단한 이분 탐색 문제였다.
먼저 꼬다리를 자른 김밥의 길이를 벡터에 넣어 주었는데 2 * K 보다 긴 경우에는 양쪽을 자르고 K보다 긴 경우에는 한
쪽만 자른다. 주의할 점이 길이가 2 * K인 김밥은 양쪽을 잘라서 없어지는 것 같다.
그다음에는 이분 탐색을 이용해서 어떤 mid에서 김밥을 m개 이상 만들 수 있는지 구하면 된다.
즉 이번 mid에서 만들 수 있는 개수가 m개 이상이라면 길이를 늘렸을 때도 m개 이상을 만들 수 있는 가능성이 있다고
보고 문제를 풀었다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 3077 임진왜란 (0) | 2021.01.21 |
|---|---|
| 백준 온라인 저지 9663 N-Queen (0) | 2021.01.13 |
| 백준 온라인 저지 1790 수 이어 쓰기 2 (0) | 2020.12.31 |
| 백준 온라인 저지 14492 부울행렬의 부울곱 (0) | 2020.12.30 |
| 백준 온라인 저지 11687 팩토리얼 0의 개수 (0) | 2020.12.27 |