정올 1816 외양간 문제풀이

정올 문제풀이

1816번 : 외양간

 

 

입력 예

4 50 18 
3 
4 
6 
8 
14 
15 
16 
17 
21 
25 
26 
27 
30 
31 
40 
41 
42 
43

 

출력 예

25

 

 

제출코드

c++

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

int main()
{
	int m, s, c;
	int rooms[200];
	int sub[200];

	scanf("%d %d %d", &m, &s, &c);
	for (int i = 0; i < c; i++)
		scanf("%d", rooms + i);

	std::sort(rooms, rooms + c);

	for (int i = 0; i < c - 1; i++)
		sub[i] = rooms[i + 1] - rooms[i] - 1;

	std::sort(sub, sub + (c - 1), std::greater<int>());

	int res = rooms[c - 1] - rooms[0] + 1;
	for (int i = 0; i < m - 1 && i < c - 1; i++)
		res = res - sub[i];

	printf("%d", res);

	return 0;
}

 

 

간단한 변수 리뷰

 

rooms (size 18) : 소가 있는 외양간 번호들

3, 4, 6, 8, 14, 15, 16, 17, 21, 25, 26, 27, 30, 31, 40, 41, 42, 43

 

sub (size 17) : (소가 있는 외양간번호 간의 차 - 1) == 연속적으로 소가 없는 외양간 개수

0, 1, 1, 5, 0, 0, 0, 3, 3, 0, 0, 2, 0, 8, 0, 0, 0

 

정렬 후 sub

8, 5, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

 

필요한 판자의 최소길이

(43 - 3 + 1) - 8 - 5 - 3 = 25

 

결과 25

 

 

풀어서 설명

 

rooms = 3, 4, 6, 8, 14, 15, 16, 17, 21, 25, 26, 27, 30, 31, 40, 41, 42, 43

배열에 위처럼 입력되었을 때

판자 1개로 외양간들을 전부 막으려면 얼마의 길이가 필요할까?

 

 

예를들어 3번부터 5번까지 막으려면 3의 길이의 판자가 필요하다

5 - 3 + 1 = 3

 

rooms 배열에서는 43 - 3 + 1 = 41

최소 41 길이의 판자 하나면 외양간들을 전부 막을 수 있다

 

그럼 판자 두개로 외양간들을 막으려면 어떻게 해야 최소 길이가 될까?

연속적으로 소가 없는 외양간들 길이가 가장 긴 곳을 제외하면 된다

 

 

위 그림의 경우 7~8번이 연속적으로 소가 없는 제일 긴 외양간들이고

3번~6번, 9번을 막는 두개의 판자 길이가 5로 가장 짧다

 

7 - 2 = 5

=> (9 - 3 + 1) - (9 - 6 - 1) = 5

 

그럼 판자 세개로 외양간들을 막는 경우 판자의 최소길이는?

 

7 - 2 - 1 = 4

=> (9 - 3 + 1) - (9 - 6 - 1) - (5 - 3 - 1) = 4

 

 

rooms 배열에 적용해보자!

rooms = 3, 4, 6, 8, 14, 15, 16, 17, 21, 25, 26, 27, 30, 31, 40, 41, 42, 43

 

3~4번 사이엔 소가 없는 외양간이 없다

4 - 3 - 1 = 0

 

4~6번 사이엔 소가 없는 5번 외양간이 한개 있다

6 - 4 - 1 = 1

 

이렇게 sub배열을 채운다

sub = 0, 1, 1, 5, 0, 0, 0, 3, 3, 0, 0, 2, 0, 8, 0, 0, 0

 

소가 없는 외양간 개수가 많은 순서대로 정렬

sub = 8, 5, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

 

m이 4 일 경우 (판자 최대 공급 개수)

계산

판자 1개 최소길이 ? 41

판자 2개 최소길이 ? 41 - 8 = 33

판자 3개 최소길이 ? 41 - 8 - 5 = 28

판자 4개 최소길이 ? 41 - 8 - 5 - 3 = 25

 

정답은 25 !!

 

 

예외처리 주의

m (판자공급개수) 이 c (소가 있는 방) 와 같거나 클 경우