[백준] 17036 - Sleepy cow Herding (c++)

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

 

문제 요약

1차원 들판에 N마리의 소 위치가 주어진다. 소를 연속된 위치에 모아야 한다(1,2,3,4 같이). 양 끝에 있는 소중 하나를 선택해서 그 소를 제외한 소들의 양 끝 위치 사이에 소가 없는 위치로 이동시킬 수 있다. 목표를 만족하는 이동횟수의 최솟값과 최댓값을 구해라.

 

풀이 (NlogN)

• 애드혹

n-연속된 좌표 n개에 최대 소 개수가 최솟값이 된다. 하나씩 끼워 넣는다 생각하면 된다. 예외가 딱 하나 있는데 1,2,3,4,7 이런식으로 하나만 2칸이상 떨어져 있으면 1이 아니고 2다. 최대는 양끝 중 하나를 두개 이상 연속하게 만들어 빈칸을 다 방문하는 것이다.

 

#include <bits/stdc++.h>
using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n; cin>>n;
	vector<int> v(n);
	for (int &i:v) cin>>i;

	sort(v.begin(),v.end());
    int l=0,mn =1e9;
	for(int i=0;i<n;i++) {
        while(v[i]-v[l]>=n) l++;
        mn =min(mn,n-i+l-1);
    }
    // if (a[n-2]-a[0]==n-2&&a[n-1]-a[n-2]>2)
    if(v[n-2]-v[0]==n-2&&v[n-1]-v[n-2]>2||
        v[n-1]-v[1]==n-2&&v[1]-v[0]>2)
        cout << 2 <<'\n';
    else
        cout << mn<<'\n';

    int blk=v[n-1]-v[0]-n+1;
    cout << max(blk-v[1]+v[0]+1,blk-v[n-1]+v[n-2]+1);
}