https://www.acmicpc.net/problem/18113
18113번: 그르다 김가놈
첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다.
www.acmicpc.net
김밥의 꼬다리를 K * 2 만큼 잘라낸 김밥을 손질된 김밥이라고 하며, K * 2보다 작은 김밥은 K만큼만 잘라낸다고 합니다.
그 손질된 김밥을 길이가 P인 조각으로 잘라내 최소 M개의 조각을 만드려고 합니다.
-> 최소 M개의 조각을 만들기 위한 최대 P를 구하는 문제로 파라매트릭 서치를 이용합니다.
파라매트릭 서치는 이분탐색과 큰 차이는 없으며,
이분탐색이 정확히 M인 값을 구하는 반면, 파라매트릭 서치는 M에 가장 가까운 최적의 값을 구하는 것입니다.
이 문제는 두 가지 방법을 선택하여 해결할 수 있습니다.
먼저, 모든 김밥에 대해 최적의 P를 구하는 방법입니다.
이 방법은 입력을 그대로 다 받아놓고, 파라매트릭 서치 과정에서 K * 2 or K를 빼는 식이 포함되는 방법입니다.
아니면, 애초에 K보다 작거나 K * 2와 같은 길이의 김밥을 먼저 제외하여 최적의 P를 구하는 방법입니다.
이 방법은 입력을 받을 때 미리 K * 2 or K를 빼는 식이 포함되는 방법입니다.
이 과정에서 꼬다리를 제거했을 때 길이가 0 이하가 되는 김밥을 제외합니다.
두 방법 모두 AC를 받는데는 문제가 없으나 두번째 방법이 더 적은 갯수로 구할 수 있으므로 시간상 이득을 볼 수 있습니다.
두 방법으로 제출했을 때 확실히 미리 제외한 방법이 시간상 효율적이었습니다.
파라매트릭 서치 과정에서는
l, r은 김밥조각의 길이인 P의 범위이며, 김밥을 m으로 나눈 몫을 카운팅한 값이 M 이상이 되는 최적의 해를 구해주시면 되겠습니다.
[필요없는 김밥을 제외하지 않은 코드]
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> list;
int N, K, M, l, r;
void func() {
int ans = -1;
l = 1;
while (l <= r) {
int m = (l + r) >> 1;
int cnt = 0;
for (int i = 0; i < N; i++) {
if (list[i] <= K) continue;
if (list[i] >= K * 2) cnt += ((list[i] - K * 2) / m);
else cnt += ((list[i] - K) / m);
}
if (cnt >= M) {
ans = m;
l = m + 1;
}
else {
r = m - 1;
}
}
cout << ans << '\n';
}
void input() {
int x;
cin >> N >> K >> M;
for (int i = 0; i < N; i++) {
cin >> x;
list.push_back(x);
r = max(r, x);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[처음부터 필요없는 김밥을 제외한 코드]
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> list;
int N, K, M, l, r;
void func() {
int ans = -1;
l = 1;
while (l <= r) {
int m = (l + r) >> 1;
int cnt = 0;
for (int i = 0; i < N; i++) {
cnt += (list[i] / m);
}
if (cnt >= M) {
ans = m;
l = m + 1;
}
else {
r = m - 1;
}
}
cout << ans << '\n';
}
void input() {
int x;
cin >> N >> K >> M;
for (int i = 0; i < N; i++) {
cin >> x;
if (x <= K || x == K * 2) continue;
int sub = x;
if (x < K * 2) sub -= K;
else sub -= (K * 2);
list.push_back(sub);
r = max(r, sub);
}
N = list.size();
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > binarysearch' 카테고리의 다른 글
| boj 27977 킥보드로 등교하기 (4) | 2023.04.22 |
|---|---|
| boj 2295 세 수의 합 (0) | 2022.06.28 |
| boj 2110 공유기 설치 (0) | 2021.04.13 |
| boj 7453 합이 0인 네 정수 (0) | 2021.01.22 |
| boj 2143 두 배열의 합 (0) | 2021.01.22 |