[문제 링크](https://www.acmicpc.net/problem/1654)
💡 이분 탐색/매개 변수 탐색
Memory: 2060KB Time: 8ms Code Length: 765B
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int K, N;
int arr[10000];
int maxV = 0;
void init() {
cin >> K >> N;
for (int i = 0; i < K; i++) {
cin >> arr[i];
if (maxV < arr[i]) {
maxV = arr[i];
}
}
}
int get_peice(long long length){
int sum = 0;
for (int i = 0; i < K; i++) {
sum += (arr[i] / length);
}
return sum;
}
long long solve() {
long long st = 1;
long long en = maxV;
while (st< en) {
long long mid = (st + en) / 2;
int result = get_peice(mid);
if (result < N) {
en = mid;
}
else if (result >= N) { // 같을 때 st의 값을 올려줘야함.
st = mid + 1;
}
}
if (get_peice(st) != N) return st - 1; // result == N 일때
return st;
}
int main() {
init();
cout << solve();
}
이 코드는 사용자로부터 입력을 받아들여 일정 길이의 나무 조각을 잘라내는 문제를 해결하는 프로그램이다. 먼저 init() 함수에서는 사용자로부터 K와 N을 입력받고, K개의 나무 조각의 길이를 배열 arr에 저장하면서 가장 긴 나무 조각의 길이를 maxV에 저장한다.
그 다음 get_peice() 함수는 주어진 길이로 나무 조각을 잘랐을 때 얻을 수 있는 조각의 개수를 계산하여 반환한다.
solve() 함수에서는 이진 탐색을 사용하여 최적의 길이를 찾는다. 초기 범위는 1부터 maxV까지로 설정하고, 이진 탐색을 통해 N개의 조각을 얻을 수 있는 최대 길이를 찾는다.
마지막으로 main() 함수에서 init() 함수를 호출하여 입력을 받고, solve() 함수를 호출하여 최적의 길이를 출력한다.
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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int K, N;
int arr[10000];
int maxV = 0;
void init() {
cin >> K >> N;
for (int i = 0; i < K; i++) {
cin >> arr[i];
if (maxV < arr[i]) {
maxV = arr[i];
}
}
}
int get_peice(long long length){
int sum = 0;
for (int i = 0; i < K; i++) {
sum += (arr[i] / length);
}
return sum;
}
long long solve() {
long long st = 1;
long long en = maxV;
while (st < en) {
long long mid = (st + en + 1) / 2;
int result = get_peice(mid);
if (result < N) {
en = mid - 1;
}
else if (result >= N) { // 같을 때 st의 값을 올려줘야함.
st = mid;
}
}
//if (get_peice(st) != N) return st - 1; // result == N 일때
return en;
}
int main() {
init();
cout << solve();
}
이렇게 생각해 볼 수도 있다.
