정올 1816 : 외양간 (c++)

* 문제 링크 :

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1089&sca=99&sfl=wr_hit&stx=1816

 

** 문제 풀이 방법

Goal) M개의 판자로 S개의 외양간에서 소가 있는 C의 외양간 판자로 가장 짧게 막기    : C개의 배열을 M개로 나눠 각 구간의 판자의 길이(끝-시작+1)의 합의 최소값 구하기   - 어떻게 M개의 구간을 나눌 것인가? bruteforce -> x   - 각 구간의 차이가 가장 큰 영역부터 나누기 <순서> 1) C 배열 생성 2) C 배열간 차이 배열 생성 3) 2)배열 내림차순 정렬 후 큰 (M-1)개의 시작점 index 확인 4) C배열의 0번부터 M개의 구간 생성 및 판자 길이 계산 5) 판자 길이 총합 반환

 

*** 코드

#include <stdio.h>
#include <algorithm>
#include <vector>

#define MAX_S 200

struct gap {
	int idx;
	int gap;
};

using namespace std;

int M, S, C;
int Clist[MAX_S];
int gap_list[MAX_S];
vector<gap> gap_C;

bool cmp(gap a, gap b) {
	return a.gap > b.gap;
}

int main() {

	freopen("jw1816_input.txt", "r", stdin);  // 입력 불러오기

	scanf("%d %d %d ", &M, &S, &C);
	//printf("M : %d, S : %d, C :%d\n", M, S, C);  입력 확인용

	int M_length = 0;
	if (M >= C) {  // 소 보다 판자가 많을 경우 소 마리수가 정답!
		M_length = C;
	}
	// 소 위치가 순서대로 들어오지 않을 수가 있다!!!!
	else {
		for (int i = 0; i < C; i++) {
			scanf("%d ", &Clist[i]);
		}
		sort(Clist, Clist + C);

		// C 외양간 배열 및 차이 배열 구하기
		for (int i = 0; i < C; i++) {
			if (i >= 1) {
				gap_C.push_back({ i, (Clist[i] - Clist[i - 1]) });
			}
		}
		sort(gap_C.begin(), gap_C.end(), cmp);

		// 각 구간별 판자 길이 구하기
		for (int i = 0; i < M - 1; i++) {
			gap_list[i + 1] = gap_C[i].idx;

		}
		sort(gap_list, gap_list + M);
		gap_list[M] = C;

		for (int i = 0; i < M; i++) {
			int start_idx = gap_list[i];
			int end_idx = gap_list[i + 1] - 1;
			M_length += Clist[end_idx] - Clist[start_idx] + 1;
		}
	}

	printf("%d\n", M_length);

	return 0;
}

 

**** 주의할 점

• 판자 개수가 '소'보다 많으면 그냥 '소' 마리수가 정답! • 입력값이 정렬이 안 된 경우도 있다!!!!

 

 

 

 

<Reference>

- http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1089&sca=99&sfl=wr_hit&stx=1816