B2110

개요

백준 문제 B2110번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 60분
https://www.acmicpc.net/problem/2110

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

코드

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

using namespace std;
const int MAX = 200001;
int home[MAX];
int maxLen = 0;
int countNum = 0;


int checkPosibleInstall(int distance)
{
	int count = 1;
	int curHome = home[0];
	for(int i=1;i<countNum;i++)
	{
		if(distance <= home[i] - curHome)
		{
			count++;
			curHome= home[i];
		}
	}
	return count;
}

void binarySearch(int start,int end,int haveToInstall)
{	
	if(start > end)
	{
		return;
	}
	int mid = (start + end) / 2;
	int installedCount = checkPosibleInstall(mid);
	if(installedCount >= haveToInstall)
	{
		maxLen = max(maxLen,mid);
		binarySearch(mid+1,end,haveToInstall);
	}
	else
	{
		binarySearch(start,mid-1,haveToInstall);		
	}



}

void solve()
{
	int N,installNum;
	cin >> N >> installNum;
	for(;countNum<N;countNum++)
	{
		cin >> home[countNum];
	}
	sort(home,home+countNum);
	int distance = home[countNum-1] - home[0];
	binarySearch(1,distance,installNum);
	cout << maxLen;
}


int main()
{
	solve();
}

풀이

* 웹에서 참고 많이한 문제

문제 풀이는 우선 동적계획법과 비슷한 느낌으로
정해진 간격을 두고 일단 설치한 뒤에 조건을 돌아보는 식으로 풀 수 있다.
자세히는 설치하는 공유기들은 이전에 설치된 공유기와 간격값이 크거나 같아야 한다.(주어진 간격보다 적으면 안되니까)
이 조건으로 우선 설치를 한 뒤에
설치할 수 있는 수와 비교하여 간격을 줄이거나 늘리는 방법으로

답을 찾을 수 있다.

배울 점, 메모

이 문제를 보고 생겼던 의문점 하나
이분 탐색인데 정렬이 안되어서 입력이 들어온다 -> 정렬해야하지 않나? => YES
logN에 풀어야하는데 기존 정렬함수는 효율적으로 잘 짜여져있어 사용해도 됨.

문제를 읽고 생각을 해봤는데 자신의 생각에 확신이 안들어 금방 포기해버렸다.
간격을 항상 같아야 한다고 생각했는데 사실 간격보다 크기만 하면 되는 것이었다.
일단 설치한 뒤에 조건을 돌아보는 방식을 생각하지 못하여서 어떻게 구현할지 조차 감이 안잡혔다.

어떻게 개선할까

• 한 문제당 최소 30분 이상은 안풀리더라도 구현하지않고 생각하자
• 생각 및 구현이 1 시간이 넘어가지 않는다면 무조건 자신감 갖고 그냥 생각한대로 구현해보자
  • 이것이 필요한 이유는 첫번째로 자신의 생각에 자신감을 갖기 위함
  • 두번째로 틀리거나 모르겠어도 배울점이 많을 것이기 때문이다