백준 C++ 1654번) 랜선 자르기

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

1654번: 랜선 자르기

단순히 이분탐색이겠지 했는데, 매개 변수 탐색이라는 알고리즘을 사용해서 푸는 문제였습니다. 매개 변수 탐색은 추후에 자료구조에 정리해서 올릴 예정입니다. 여기서 코드는 다 짯는데 계속 틀려서 무슨 문제인지 확인해본 결과

 

K=3 N=3 300 300 300 이 입력될 경우, 단순하게 end = max 로 코드를 짤 경우 299가 출력되는 결과가 존재하더라구요. 그래서 end = max + 1로 하여 확실하게 불가능한 수로 만들어서 해결하였습니다.

 

어떻게 감을 잡아야지 하시는 분들은 매개 변수 탐색을 공부해보시고 푸시면 도움이 확실히 많이 됩니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

typedef long long int64;

int main() {
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	
	int K, N;
	vector<int64> t1;
	cin >> K >> N;
	int64 max = 0;
	for (int i = 0; i < K; i++) {
		int64 s;
		cin >> s;
		t1.push_back(s);
		if (max < s)
			max = s;
	}
	int64 start = 1;
	int64 end = max+1;
	while (start+1 < end) {
		int64 total = 0;
		int64 mid = (start + end) / 2;
		for (int i = 0; i < K; i++) {
			total += (t1[i] / mid);
		}
		if (total >= N)
			start = mid;
		else
			end = mid;
	}
	cout << start;
}