[C/C++ : JUNGOL] 1816번 - 외양간

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1089&sca=3050 

JUNGOL

 

 

1. 입력 받은 것들 정렬

2. 사이 거리 모두 구해준 후 내림차순 정렬

3. [사용 가능한 판자 개수 - 1]개를 위에서 정렬한 인덱스 위치로 자르기 

    -> 사이 거리가 큰 것을 순서대로 자른다는 의미

except) 만약 외양간 수보다 판자 개수가 더 크다면 외양간 수를 바로 반환해주면 된다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int M, S, C;
bool flag[300];
vector<int> ps;

bool cmp(pair<int, int> lhs, pair<int, int> rhs) {
	if (lhs.second == rhs.second) return lhs.first < rhs.first;
	return lhs.second > rhs.second;
}

void input() {
	cin >> M >> S >> C;
	for (int i = 0; i < C; i++) {
		int x; cin >> x;
		ps.push_back(x);
	}
}

int boardLength(vector<int> &chk) {
	int answer = 0;
	sort(chk.begin(), chk.end());
	int startIndex = 0;
	for (auto t : chk) {
		answer += ps[t - 1] - ps[startIndex] + 1;
		startIndex = t;
	}
	answer += ps[C - 1] - ps[startIndex] + 1;
	return answer;
}

int solution() {
	if (M >= ps.size()) return ps.size();
	sort(ps.begin(), ps.end());
	vector<pair<int, int>> ifm;
	for (int i = 1; i < C; i++) {
		ifm.push_back({ i, ps[i] - ps[i - 1] });
	}
	sort(ifm.begin(), ifm.end(), cmp);
	vector<int> chk;
	for (int i = 0; i < M - 1; i++) {
		chk.push_back(ifm[i].first);
	}
	
	return boardLength(chk);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}