[C/C++] 백준 1654번 랜선 자르기 / 이분 탐색 알고리즘 - (1)

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

랜선 자르기 

 

시간 제한 2 초

메모리 제한 128 MB

제출 60448

정답 13186

맞은 사람 8508

비율 20.165%

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이

문제를 천천히 읽어보면, 이분탐색으로 풀 수 있다는 힌트가 있는 문제였습니다.

K개의 랜선을 가지고 있고, 이를 이용해 N개의 랜선을 만드려한다. 단, N개의 랜선의 길이는 모두 같아야한다.

N개의 랜선을 만들 때, 가장 길게 만들 수 있는 랜선의 길이는 얼마인가? 를 구하는 문제입니다.

 

문제를 처음 읽어보셨을 때, 1부터 랜선 최대길이까지 모두 탐색해보면 답이 나오지 않나? 라는 생각이 드셨을겁니다.

그러나 랜선의 길이는 1~2,147,483,647이므로, 너무나 많은 경우가 존재합니다. 이를 위해서 우리는 이분탐색 이라는 탐색 기법을 알아볼 필요가 있습니다.

 

 

이 문제를 풀기 위해서는 이분 탐색 알고리즘에 대해서 알아야 합니다.

 

이분 탐색이란?

즉, 탐색할 배열을 반으로 나누어 가며 탐색하는 기법입니다. 

https://charles098.tistory.com/133

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

 

이분 탐색에 대해 더 알고싶은 분들은 위 글 참고하면 된다.

 

1654번 랜선 자르기 전체 코드 

이 코드에서 주의할 점은 딱 n개를 찾는 것이 아니라 n개 보다 커도 되니 짜르는 수의 max 값을 찾는 것이다. 

따라서 n개 짜르는 값을 찾았다고해서 거기서 종료하면 안되고, 조건에 맞는 더 큰 값이 있는지 찾아야한다는 점이다. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n, k;

	cin >> k >> n;
	vector<unsigned long long> vec;
	unsigned long long minn = 0;

	for (int i = 0; i < k; i++) {
		unsigned long long num;
		cin >> num;
		vec.push_back(num);
		if (num > minn) minn = num;
	}
	
	unsigned long long front = 1;
	unsigned long long back = minn;
	unsigned long long point = (minn+1) / 2;

	unsigned long long ans=0;
	int flag = 0;
	while (front<= back) {
		unsigned long long result = 0;
		for (int i = 0; i < vec.size(); i++) {
			result += vec[i] / point;
			if (result > n) break;
		}

		if (result >= n) {
			ans = max(ans, point);
			front = point + 1;
			point = (front + back) / 2;

		} 
		else if (result < n) {
			back = point-1;
			point = (front + back) / 2;

		}
	}

	cout << ans;
	return 0;
}