백준 1654번 : 랜선 자르기

문제 접근

---

이분 탐색으로 풀면 되는 문제다. 되게 간단한 문제인데 이분 탐색의 세부적인 구조를 제대로 구현하지 못해서 삽질을 많이 했다. 그냥 ans 변수 하나 만들어서 대입해주면 되는건데.. 그래도 이런 저런 테스트 케이스 만들어보는 연습도 되었고, 탐색 구조를 생각해보게 되어 나쁘지만은 않았다. 

 

랜선이 N 개가 되려면 K 개 랜선의 총 길이 / N 보다는 작거나 같아야 하기에 total/N 까지 탐색했다. 간단하게 lgN 번 동안 K 개의 랜선으로 길이가 mid 인 랜선을 얼마나 만들 수 있는지 확인하고, N 개 만큼 만들지 못하면 mid 보다 작은 길이를 탐색, N 개 이상 만든다면 ans 에 mid 를 저장하고 mid 보다 긴 길이를 탐색한다.

 

왜 이걸 못해서 그렇게 틀렸지.. 코드를 재설계하기보다는 답을 끼워맞추려고 코드를 덧붙인 느낌으로 접근해서 그런 것 같다. 그냥 깔끔하게 다시 생각하고 풀었으면 훨씬 빨리 풀 수 있었을텐데..

 

 

문제 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll K, N, ans, total=0;
int arr[10001];

ll bs_length(ll s, ll e)
{
	if(s > e)
		return 0;
	
	ll mid = (s+e)/2;
	ll cnt = 0;
	
	for(int i=0; i<K; ++i)
		cnt += arr[i]/mid;
	
	if(cnt < N)
		return bs_length(s, mid-1);
	
	else
	{
		ans = mid;
		return bs_length(mid+1, e);
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>K>>N;
	
	for(int i=0; i<K; ++i)
	{
		cin>>arr[i];
		total+=arr[i];
	}
	
	bs_length(1ll, total/N);
	
	cout<<ans<<'\n';
	
	return 0;
}

 

테스트 케이스

---

1)
1 1
219

ans : 219

2)
1 50
50

ans : 1

3)
1 50
150

ans : 3

 

결과

---

눙물 ㅠㅠ