[백준/BOJ] 18880번 Social Distancing I

오랜만에 알쿡에 참여하면서 풀었던 문제들을 하나씩 정리해 보고자 한다.

 

아이디어는 그전에 푼 문제와 비슷해서 금방 풀줄 알았는데, 예외처리때문에 많이 틀렸다ㅜㅜ

 

 

<문제>

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

18880번: Social Distancing I

 

 

우선 문제해석은

 

N(2<=N<=10^5)을 입력 받고, 다음줄에 N개 만큼의 헛간의 상태가 1또는 0으로 들어온다.

 

1일 경우 소가 있는 상태, 0일 경우 소가 없는 상태를 의미하고 기존의 상태에서 소 2개를 추가하여 

 

소들간의 거리들의 최소값이 최대가되는 거리 D를 구하는 문제이다.

 

 

풀이는 먼저 푼 친구가 이분 탐색이라 얘기해줘서 감이왔다.

 

1. 기존의 소들 사이에 거리차이 최소 D만큼 갖는 소를 몇개를 추가할 수 있는지 구한다.

     1) 000...1 인 첫부분

     2) 1000...0001 인 중간부분

     3) 1000...000 인 끝부분

이렇게 3가지 경우에서 거리차이 D로 새로운 소를 넣을 수있는 경우를 모두 더해

2마리보다 같거나 크다면 D를 늘리고, 작다면 D를 줄여서 D의 최대값을 구한다.

 

 

2. 구한 D보다 기존의 소들간의 거리가 더 작을 수있다.(예외 1)

따라서 구한 D와 기존의 거리차이를 비교해 작은 값을 출력한다.

 

3. 소들이 아예 없이 모두 0을 입력받을 경우 새로 추가되는 소들의 위치는 끝과 끝에 배치해야한다.(예외 2)

그래야 거리의 최소값이 최대가 된다.

 

 

<정답 코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<math.h>
#include<stack>
#include<map>
#include<string.h>
#include<cmath>
#include<deque>
using namespace std;

int main(void) {
	int N;
	scanf("%d ", &N);
	vector<int>cow;
	int gap = 1000000;
	int re = 0;
	for (int i = 0; i < N; i++) {
		int a;
		scanf("%1d", &a);
		if (a == 1)cow.push_back(i+1);
	}
	if (cow.size() > 0) {
		for (int i = 1; i < cow.size(); i++) {
			gap = min(gap, cow[i] - cow[i - 1]);
		}
		int L = 1, R = N;	
		while (L <= R) {
			int mid = (L + R) / 2;
			int cnt = 0;
			for (int i = 0; i < cow.size(); i++) {
				int p = 0;
				if (i == 0) {
					p += (cow[i] - 1) / mid;
				}
				else p = (cow[i] - cow[i - 1]) / mid > 0 ? ((cow[i] - cow[i - 1]) / mid) - 1 : 0;

				cnt += p;
			}
			cnt += (N - cow[cow.size() - 1]) / mid;
			if (cnt >= 2) {
				L = mid + 1;
				re = mid;
			}
			else {
				R = mid - 1;
			}

		}
	}
	else {
		re = N - 1;
	}
	printf("%d\n", min(re,gap));
	return 0;
}