백준 - 17036 Sleepy Cow Herding (Silver) (C++, Cpp)

1. 문제소개

1-1.  요구사항

• 소의 총 마릿수 N이 처음 입력으로 들어옴
• 소들은 2차원 좌표 평면상에 존재하고 서로 겹쳐있지 않음
• 소들은 좌표상에 존재하는 다른 소들 사이로 이동할 수 있는데, 이동 시 맨 앞이나 맨 뒤로 이동은 불가능함
• 소들이 모두 줄지어 서있을 수 있도록 움직이는 최소 횟수와 최대 횟수를 각각 출력해야 함

1-2.  입력값과 출력값

// 예제 입력

3 // 총 소 마릿수

7 // 한 소는 x좌표 7에 위치함
4 // 한 소는 x좌표 4에 위치함
9 // 한 소는 x좌표 9에 위치함

// 예제 출력
1 // 4에 위치한 소가 8로 한번 이동하면 최소 횟수 1만족
2 // 9에 위치한 소가 5로 한번 이동하고 4에 위치한 소가 6으로 이동하면 최대 횟수 2만족

 

• 첫째 줄에는 소의 총 마릿수 N(1 ≤ N ≤ 10 ^ 5)이 주어짐 (시간제한이 2초이므로 N^2 시간 복잡도로는 풀 수 없음)
• 각 N개의 줄에 각각 소의 위치 정보가 주어짐
• 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어짐
• !주의 : 소는 처음 부터 정렬이 이미 완료된 상태일 수도 있고, 순서가 보장된 채로 입력이 들어오지 않음!
• 소를 전부 빈자리 없이 일렬로 세우기 위한 최소 횟수와 최대 횟수를 출력

2.문제풀이

2-1.  준비물

• (1) 총 소의 수, 하나로 묶이는 확인이 끝난 소의 위치 정보(idx), 하나로 묶이는 소들의 최대 숫자, 하나로 묶인 소들 사이에 빈자리가 있는지 확인하는 불리언 변수, 소들의 위치 정보를 받을 벡터, 최대 이동 횟수를 구하기 위한 소들간의 간격을 저장하는 벡터

int n // 총 소의 숫자
int idx = 0; // 매번 순회를 하면 시간초과가 걸리기 때문에 한번의 최적화를 위한 변수다. 아래에서 보충 설명
int max_cluster = 1; // 하나로 묶어줄 소들의 최대 숫자. 매번 갱신해준다.
// 1로 초기화한 이유는 한 묶음의 소집합은 최소 한 마리의 소가 있기 때문이다.
	
bool empty = false; // 찾은 최대 군집의 소들이 현재 빈자리를 포함하고 있는 확인하는 변수. 아래에서 보충 설명
vector<int> vec(n); // 소들의 위치를 입력받을 벡터
vector<int> diff(n); // 각 소들이 서로 떨어진 거리를 저장하는 벡터. 최대 횟수를 구할 때 사용한다

• (2) 소들의 정보를 입력받고 정렬, 이웃한 소들끼리 떨어진 거리를 구해준다

	for (int i = 0; i < n; i++)
		cin >> vec[i]; // 소 위치 입력
    
	sort(vec.begin(), vec.end()); // 순서가 보장되지 않으므로 정렬
    
	for (int i = 1; i < n; i++)
		diff[i] = vec[i] - vec[i - 1] - 1; // 정렬된 소들의 떨어진 거리를 저장

• (3) 최소 이동 횟수를 구하는 로직

	for (int i = 0; i < n; i++) { // 각 소들을 한번씩 순회한다. (소들을 하나로 묶었을 때, 시작위치에 있는 소를 의미한다.)
		if (idx >= n) // 모든 소가 확인이 완료되면 반복문을 종료한다.
			break;  
		for (;idx < n; idx++) { // 우리가 확인할 idx의 소가 한 묶음으로 묶일 수 있는 지 확인하는 반복문
			if (i == idx) // 확인한 소가 시작 위치의 소와 같으면 continue
				continue;
			if (vec[idx] - vec[i] >= n) // 확인한 소와 시작 소의 거리가 n(총 소의 수)보다 크거나 같으면
				break;					// 해당 소는 한 묶음에 묶일 수 없으므로 break
		}
		if (idx - i > max_cluster) { // 한 묶음에 묶인 소의 총 마릿수는 idx - i 이다.
			max_cluster = idx - i; // 최대값 갱신
			if (vec[idx - 1] - vec[i] + 1 != max_cluster) // 만약 한 묶음의 소가 빈공간 없이 일렬로 있지 않다면
				empty = true; // empty 는 true
			else
				empty = false; // 일렬로 빡빡하게 있어서 이미 빈 공간이 없다면 empty는 false
		}
		else if (idx - i == max_cluster) { //만약 어떤 묶음이 최대 묶음의 수와 동일하다면
			if (!empty) {
				if (vec[idx - 1] - vec[i] + 1 != max_cluster)
					empty = true; //빈 공간이 있으면 최소 횟수를 줄일 수 있으므로 empty를 한번 확인해 준다
			}
		}
	}
	int min_value = n - max_cluster; // 최소 횟수는 한 묶음으로 묶인 소사이로 그렇지 못한 소들이 옮겨지는 것이다.
    // 그러므로 최소 횟수는 총 소의 수 (n) 에서 한 묶음의 최대 마리의 소 (max_cluster) 를 빼준 값이 된다.
    
	if (!empty && min_value == 1) // 예외 처리를 위한 문장이다.
		min_value++; // 만약 빈공간이 없고 한 마리의 소만 일렬로 있지 않다면 이는 예외에 해당한다.
        
        // 예를 들어 1 4 5에 소가 있다고 한다면 4와 5는 이미 일렬로 존재하지만
        // 1이 움직일 공간이 없다. (소는 소 사이로만 이동할 수 있다.)
        // 그래서 5가 1이 움직일 공간을 만드는 데 횟수 1번, 1이 움직이는데 횟수 1번으로 총 2번이 걸린다.

• (4) 최대 횟수를 구하는 로직

	int max_value = 0; // 0으로 초기화 한다.
	for (int i = 1; i < n; i++)
		max_value += diff[i]; // 이미 정렬된 이웃한 소들의 위치를 저장한다.
	if (max_value != 0) // 이미 빈 공간없이 일렬로 서있지 않는 경우 이 조건문으로 들어온다.
		max_value -= (diff[1] > diff[n - 1] ? diff[n - 1] : diff[1]);
        // 우리는 모든 소들의 떨어진 거리를 한칸씩 이동하며 최대 횟수를 구하는데,
        // 처음 이동은 한칸씩 이동이 불가능하다.
        // 그래서 양 끝에서 적게 움직이는 소를 움직여서 최대값을 만들어야 한다.
        // 즉 max_value에서 양 끝의 소가 적게 움직이는 만큼 빼준다.

• (4) 정답을 출력

cout << min_value << "\n" << max_value; // 순서대로 출력

2-2.  풀이방법

1) 소들이 최소 한번은 움직여야 하는 경우의 최소 횟수 구하는 로직. 

• 가장 움직여야 할 소가 1마리인 경우와 아닌 경우를 구분해야 한다.
• 1마리가 아닌 경우 부터 보자면 우리는 소가 n 마리 있다면, 일렬로 섰을 때, 첫번째 소의 위치 X_1 과 N번째 소의 위치 X_N 사이에 수식이 하나 만족 하는 것을 안다. (간단히 이야기해서 소 5마리를 일렬로 정렬하면 그 무리의 길이는 5라는 소리다.)
• X_N - X_1 + 1 = n
• 즉 우리는 움직이지 않아도 될 소의 마릿수를 최대로 하는 것이 선행되면, 최소 움직임으로 소를 일렬로 세울 수 있다.
• 첫 번째 소부터 n만큼 떨어진 소들을 전부 모아서 가장 많이 모이는 묶음을 찾는다.
• 만약 소의 마릿수가 같은 묶음이 여러개 존재한다면 빈칸이 있는 묶음을 우선으로 한다. (움직이는 소가 한 마리일 경우 예외처리 용)
• 아래 이미지는 빈칸이 있는 경우 최소 로직으로 소가 일렬로 정렬 되는 경우다

움직여야 할 소가 1마리 보다 많고 빈칸이 있는 경우 최소 로직

• 움직이는 소가 한 마리만 아니라면 빈칸의 존재나 부족함과 상관 없이 움직여야할 소의 숫자가 최소 움직임 횟수다.!

움직여야 할 소가 1마리 보다 많고 빈칸이 없는 경우 최소 로직

• 하지만 움직여야 할 소가 한 마리라면 위 로직에 모순이 생긴다.
• 2마리 이상부터는 한 마리가 빈 공간을 만들고 나머지 소들이 그 만들어진 공간에 들어가는데, 한 마리인 경우는 소는 반드시 소와 소 사이로 움직여야 한다는 제약 때문에, 처음으로 행동할 수 없다.
• 그래서 이미 일렬로 존재하는 소 중에서 한 마리가 자신의 공간을 비우며 이동하고, 그 공간에 움직여야 할 소 한마리가 들어가서 총 2번의 이동이 필요하다.
• 그 예외 처리가 if (!empty && min_value == 1) 이 부분이다.
• [추가] 애초에 무리에 빈공간이 존재했다면 움직여야 할 한 마리의 소가 그 공간으로 이동하면 되므로 한 번만에 이동이 가능하다.
• 위 예외는 무리 속에 빈공간이 존재하지 않으며 무리에서 벗어난 (다른 말로 움직여야 할) 소가 한 마리인 경우에만 해당한다.

빈칸이 없고 움직여야 할 소가 한 마리인 경우

빈칸이 없고 움직여야 할 소가 한 마리인 경우2

2) 소들이 최소 한번을 움직여야 하는 경우 최대 횟수 구하는 로직

• a b c 이렇게 소가 있을 때 어떻게 가장 많이 움직이면서 일렬로 설 수 있을 지는 간단하다.
• a가 b + 1 로 가고 b 가 현재 a의 위치인 b + 1의 옆자리인 b + 2 로 가고 이렇게 한칸씩 번갈아가면서 c 의 곁으로 가면 된다.
• 여기서 유의할 점은 가장 처음 이동은 한 칸씩 이동이 불가능 하고 반드시 다른 소 2마리의 사이로 이동해야 한다는 점이다.
• 그래서 양 끝 소들의 이동중에 짧게 이동하는 소가 먼저 움직이고 그 다음부터는 모든 소가 정렬 될 때까지 한칸씩만 번갈아가면 이동하면 되므로, max_value 는 diff들은 전부 합한 값에 diff[1]과 diff[n-1] 중 작은 값을 빼주면 된다.
• [추가] => 예를 들어 1번소가 3에 위치하고 2번 소가 6에 위치할 때 1번소는 7로 움직인다.
• 이 경우 1번 소와 2번 소의 원래 사이 거리는 2이고 diff는 3인데 왜 diff를 빼주는 걸까?
• 이는 1번 소가 이동하면서 2번소와 3번소의 사이 거리 한칸을 추가로 제거 하기 때문이다!

최대 소가 움직이는 로직

3) 애초에 소들이 빈 공간없이 일렬로 서 있을 경우는 최소 횟수가 0이고 최대 횟수가 0이다. 

• 예외처리가 필요한 부분이다.
• 최소 횟수의 경우 max_cluster의 값과 n 값이 동일하게 되고 n은 3이상의 값이 보장되므로 최소 횟수 로직의 마지막 줄인 min_value++ 조차 동작하지 않는다. 그래서 0이 잘 출력됨을 알 수 있다.
• 최대 횟수의 경우 diff가 모조리 0이므로 max_value가 처음부터 0인 경우에 해당하므로 잘 출력된다.

3. 전체 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

int main()
{
	fast;
	int n, idx = 0;
	int max_cluster = 1;
	bool empty = false;
	cin >> n;
	vector<int> vec(n);
	vector<int> diff(n);
	for (int i = 0; i < n; i++)
		cin >> vec[i];
	sort(vec.begin(), vec.end());
	for (int i = 1; i < n; i++)
		diff[i] = vec[i] - vec[i - 1] - 1;

	for (int i = 0; i < n; i++) {
		if (idx >= n)
			break;
		for (;idx < n; idx++) {
			if (i == idx)
				continue;
			if (vec[idx] - vec[i] >= n)
				break;
		}
		if (idx - i > max_cluster) {
			max_cluster = idx - i;
			if (vec[idx - 1] - vec[i] + 1 != max_cluster)
				empty = true;
			else
				empty = false;
		}
		else if (idx - i == max_cluster) {
			if (!empty) {
				if (vec[idx - 1] - vec[i] + 1 != max_cluster)
					empty = true;
			}
		}
	}
	int min_value = n - max_cluster;
	if (!empty && min_value == 1)
		min_value++;
	int max_value = 0;
	for (int i = 1; i < n; i++)
		max_value += diff[i];
	if (max_value != 0)
		max_value -= (diff[1] > diff[n - 1] ? diff[n - 1] : diff[1]);
	cout << min_value << "\n" << max_value;
}