[백준/BOJ] 백준 1114번 : 통나무 자르기

2023. 10. 18. 18:10알고리즘 문제풀이

https://www.acmicpc.net/problem/1114

 

1114번: 통나무 자르기

첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출

www.acmicpc.net

 

통나무의 가장 큰 길이가 특정 값 이하로 만들 수 있는지 확인하는 이분 탐색 (매개 변수 탐색)을 이용해서 문제를 해결했다.

 

코드

#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;
}