그리디 - 1931.회의실 배정

phoenixKim·2022년 7월 25일
0

백준 알고리즘

목록 보기
44/174

최근 풀이 240130

: pq 사용했더니 3퍼센트에서 틀림


언제 품 ?

  • 220914 13:14 ~ 13:46

풀이 전략

  • 들어오는 시간을 기준으로 하기에는 int,out 시간이 길수록 ,
    최대 들어오는 회의실 수가 작아지므로, 옳지 못함.

  • 그림을 그렸을 때 , 나오는시간을 기준으로 해서 만들수 있지 않을까? 란
    생각을 했음.

  • 그러면서 , 나오는 시간과 들어가는 시간 간격을 기준으로 접근하면 되지 않을까? 라는 생각을 했고, 밑의 그림을 그림.

코드

  • 1) 정렬 후에 0번째 인덱스를 집어넣고, second가 다음 second보다 크거나
    동일하면 무조건 집어넣음.

  • 2 - 1) 그렇게 해서 12 8 이 들어감. 11과 8을 비교해야 하는데
    이렇게 생각할 수 있음. 동일한 second에서는
    diff가 더 작은 것이 들어와야 회의실에 들어가는
    빈도수가 더 높아짐. 일단 이렇게 만 생각을 함.

  • 2 - 2) 이후에 다 패스된 후, 8과 3이 들어감. 이렇게 될 경우
    여기서 총 3회로 끝나버림. 뒤에 오는 인덱스의 원소들은 들어 갈 수 없음.

  • 2 - 3) 힌트를 보면 5,7 // 1,4 가 들어감.

  • 2 - 4) 8 , 3이 들어간 상황에서, second값 3보다 다음 second값이 더 크다고 한다면???? 한 원소에서의 diff 차이가 더 작아지게 되고, 이렇게 되면,
    빈도수가 더 많아지지 않을까란 생각을 하게 됨.
    --> 이유 : second값은 항상 first값보다 작은 상황임.
    그런데 현 원소의 second보다 다음 second가 더 크다라는 의미는
    diff차이가 반드시 작을수 밖에 없다라는 의미임.


결론 , 변경해야 할점.

: 반례를 생각할 수 없다면, 시퀀스를 바꿔보는 것도 나쁘지 않음!
second값을 가장 낮게 설정하는 방식으로 바꾸고 싶으므로.
second를 그냥 sort의 대상이 되도록 벡터의 first값으로
변경해서 시도하도록 하자.
sort는 first를 디폴트로 해서 변경하므로.

놓친 부분

  • 문제에서 시작 시간과 마지막시간이 동일할 수 있다고 함.

반례
3
1 3
3 4
4 4
https://www.acmicpc.net/board/view/93999

compare 함수를 변경함.

: 반례에 대해서 생각할 수 없으니 시퀀스를
바꾸는 시도를 해보는게 더 빠를 수 있음.


#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>

#include <queue>

bool compare(pair<int, int>a, pair<int, int>b)
{
	// 만약세 second 값이 동일할 경우는 어떻게 할것인가.
	if (a.second == b.second)
	{
		// first값이 큰 값이 우선순위가 되도록 하자.
		return a.first < b.first;
	}
	return a.second < b.second;
}

int main() 
{
	// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	//   1      4
	//       3   5
	// 0           6
	//			 5   7
	//       3          8
	//           5        9
	//             6        10
	//                  8      11
	//                  8         12
	//      2                     13      
	//                            12    14
		
	// pair 값으로 입력을 한 다음에
	// 동일한 sort 한 다음에
	// 동일한 first에서 가장 작은 second값일 경우에.
	// 넣어둠.

	int n;
	cin >> n;
	vector<pair<int, int>>v(n);
	

	for (int i = 0; i < n; ++i)
	{
		cin >> v[i].first >> v[i].second;
	}

	sort(v.begin(), v.end(), compare);

	int from = v[0].first;
	int to = v[0].second;
	int ret = 1;

	for (int i = 1; i < n; ++i)
	{
		if (to > v[i].first)
			continue;

		from = v[i].first;
		to = v[i].second;
		++ret;

		// 88퍼센트에서 틀려서 다른 로직으로 만들어보자.
		//if (to <= v[i].에first)
		//{
		//	from = v[i].first;
		//	to = v[i].second;
		//	++ret;
		//}


		//cout << v[i].first << ' ' << v[i].second << endl;
	}
	cout << ret;
	// 0 6부터 들어오게 되면, 답이 3 밖에 안됨.
	// 시작값이 1,4가 들어오게 해야 함. 

	// 생각 회의실에 입장하는 순서가 중요한 게 아니라.
	// 나가는 순서가 가장 낮은순으로 정렬을 한다면.
	// 알아서 최대 빈도수를 구할 수 있을 듯 함.

}
코드를 입력하세요

88?% 에서 틀림..


#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#include <iostream>

#include <queue>

bool compare(pair<int, int>a, pair<int, int>b)
{
	return a.second < b.second;
}

int main() 
{
	// 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
	//   1      4
	//       3   5
	// 0           6
	//			 5   7
	//       3          8
	//           5        9
	//             6        10
	//                  8      11
	//                  8         12
	//      2                     13      
	//                            12    14
		
	// pair 값으로 입력을 한 다음에
	// 동일한 sort 한 다음에
	// 동일한 first에서 가장 작은 second값일 경우에.
	// 넣어둠.

	int n;
	cin >> n;
	vector<pair<int, int>>v(n);
	

	for (int i = 0; i < n; ++i)
	{
		cin >> v[i].first >> v[i].second;
	}

	sort(v.begin(), v.end(), compare);

	int from = v[0].first;
	int to = v[0].second;
	int ret = 1;

	for (int i = 1; i < n; ++i)
	{
		if (to <= v[i].first)
		{
			from = v[i].first;
			to = v[i].second;
			++ret;
		}


		//cout << v[i].first << ' ' << v[i].second << endl;
	}
	cout << ret;
	// 0 6부터 들어오게 되면, 답이 3 밖에 안됨.
	// 시작값이 1,4가 들어오게 해야 함. 

	// 생각 회의실에 입장하는 순서가 중요한 게 아니라.
	// 나가는 순서가 가장 낮은순으로 정렬을 한다면.
	// 알아서 최대 빈도수를 구할 수 있을 듯 함.

}

근복적인 이유

회의실에서 퇴장하는 시간이 작아야 한다는 것에 초점을 두어야 함.
왜냐하면 일정한 시간에 많은 회의실을 사용해야 하므로.
퇴장 시간이 낮을수록 더 많은 회의실 사용이 가능함.
그래서 퇴장시간을 기준으로 해서 정렬을 함!

그리고 입장시간을 기준으로 해서 다음에 들어올 시간을 정함.

첫번째 코드 풀이

#include <iostream>
#include <vector>
using namespace std;
#include<algorithm>

int main()
{
// 일단 정렬을 한 다음에...
// 맨 앞에 있는것부터 마지막 까지 돌리면서

int n;
cin >> n;
vector<pair<int, int>>v(n);

for (int i = 0; i < n; ++i)
{
	cin >> v[i].first >> v[i].second;
}

sort(v.begin(), v.end());

int start = 0;
int end = 0;

for (int i = 0; i < n; ++i)
{
	// 맨앞에서부터 뒤에 까지 시작하는 반복문.
	start = v[i].first;
	end = v[i].second;

	for (int j = i + 1; j < n; ++j)
	{
		int nStart = v[j].first;
		int nEnd = v[j].second;


	}


}

}

-> from의 값으로 정렬 한다음에, 이중포문 식으로 돌리려고 했는데, 
이렇게 하면 , 효율성이 좋지 못하다라는 것을 생각함.

: 큰돌님이 효율성, 시간복잡도가 높다고 생각하면, 다른 방법으로 시도해보라고 하심... 

## 많이 생각해야함. 
![](https://velog.velcdn.com/images/kwt0124/post/8bd27029-15e3-4336-a69c-cfbf196cb016/image.png)
-> 위 상태로 진행하면, 
1 , 4 -> 5 , 7 // 5 , 9 -> 경우의 수가 2개로 갈라짐.. 이부분을 처리하려면 또 복잡해짐.
-> 어떻게 하면 간단히 처리할 수 있을까를 생각해야함...


## 힌트를 활용하자. 
![](https://velog.velcdn.com/images/kwt0124/post/2711f7c5-8db1-46a7-82e7-fd9b785c4d3a/image.png)

![](https://velog.velcdn.com/images/kwt0124/post/3f07f491-4cb7-4405-be4f-780c5f320e47/image.png)

: from ~ to 에서 to 시간대로 정렬을 한다음에 처리를 하고 있는데,,,
어렵다..



profile
🔥🔥🔥

0개의 댓글

관련 채용 정보