[백준/BOJ] 백준 1114번 : 통나무 자르기
2023. 10. 18. 18:10ㆍ알고리즘 문제풀이
https://www.acmicpc.net/problem/1114
통나무의 가장 큰 길이가 특정 값 이하로 만들 수 있는지 확인하는 이분 탐색 (매개 변수 탐색)을 이용해서 문제를 해결했다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int l, k, c;
vector<int> point;
//통나무의 최대 길이가 max_len 이하가 되도록 만들 수 있는지 확인
bool check(int max_len) {
int cut_cnt = 0; //자른 횟수
int here_point = 0;
while (here_point < point.size() - 1) {
for (int j = here_point + 1; j < point.size(); j++) {
int check_len = point[j] - point[here_point];
//통나무 길이가 max_len을 넘어갈 때
//j-1지점을 자른다
if (check_len > max_len) {
int cut_point = j - 1;
if (here_point == cut_point) { //구간 하나 자체가 max_len보다 클때
return false;
}
cut_cnt++;
here_point = j - 1;
break;
}
if (j == point.size() - 1) {
here_point = point.size();
break;
}
}
}
if (cut_cnt > c) {
return false;
}
return true;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> l >> k >> c;
for (int i = 0; i < k; i++) {
int input;
cin >> input;
point.push_back(input);
}
point.push_back(0); //통나무 시작 지점도 넣기
point.push_back(l); //통나무 끝 지점도 넣기
//중복 제거
sort(point.begin(), point.end());
point.erase(unique(point.begin(), point.end()), point.end());
//통나무의 가장 큰 길이를 mid 이하로 만들 수 있는지 이분 탐색을 시행한다 (매개 변수 탐색)
int left = 0;
int right = l;
int result1 = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (check(mid)) {
result1 = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
//통나무의 최대 길이가 result1일때, 가장 처음 자를 수 있는 가장 빠른 위치를 찾는다
int result2 = -1;
for (int i = 1; i < point.size() - 1; i++) {
int first_cut_point = i; //i위치를 자른다고 가정
int check_len = point[i];
if (point[first_cut_point] > result1) {
break;
}
int cut_cnt = 1; //자른 횟수 (first_cut_point를 잘랐다고 가정)
int here_point = first_cut_point;
while (here_point < point.size() - 1) {
for (int j = here_point + 1; j < point.size(); j++) {
int check_len = point[j] - point[here_point];
//통나무 길이가 result1을 넘어갈 때
//j-1지점을 자른다
if (check_len > result1) {
int cut_point = j - 1;
if (here_point == cut_point) { //구간 하나 자체가 result1을보다 클때
here_point = point.size();
break;
}
cut_cnt++;
here_point = j - 1;
break;
}
if (j == point.size() - 1) {
here_point = point.size();
break;
}
}
}
if (cut_cnt <= c) {
result2 = point[first_cut_point];
break;
}
}
cout << result1 << " " << result2 << "\n";
return 0;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 1377번 : 버블 소트 (1) | 2023.10.18 |
---|---|
[백준/BOJ] 백준 8872번 : 빌라봉 (1) | 2023.10.18 |
[백준/BOJ] 백준 11049번 : 행렬 곱셈 순서 (1) | 2023.10.18 |
[백준/BOJ] 백준 15758번 : Milking Order (1) | 2023.10.18 |
[백준/BOJ] 백준 16947번 : 서울 지하철 2호선 (0) | 2023.10.18 |