03.07. 멀티탭 스케줄링[Greedy Algorithm][백준 1700]

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

 

Algorithm classification : Greedy Algorithm

 

03.07.1. Problem

Jun-gyu, who lives in the dormitory, uses one multi-tap. Junkyu is experiencing the inconvenience of unplugging and plugging in various electrical appliances while using multiple electrical appliances such as keyboards, hair dryers, cell phone chargers, and digital camera chargers. So, by analyzing his life pattern, Jun-gyu found out the order of use of the electric appliances he is using, and based on this, he devised a method to minimize the number of unplugging and tries to create a more comfortable living environment. For example, when using a 3-prong (three-hole) multi-tap, if the order of use of electrical appliances is given as follows,

1. keyboard

2. hair dryer

3. cellphone charger

4. digital camera charger

5. keyboard 

6. hair dryer

It is best to unplug the phone charger before plugging in the digital camera charger after plugging the keyboard, hair dryer, and cell phone charger into the multi-tap in that order, so you only need to unplug it once.

 

03.07.2. Input limit

In the first line, the number of multi-tap holes N (1 ≤ N ≤ 100) and the total number of uses of electrical appliances K (1 ≤ K ≤ 100) are given as integers. In the second line, the names of electrical appliances are given as natural numbers less than or equal to K, in order of use. All integers on each line are separated by a space character.

 

03.07.3. Output

Print the minimum number of unplugging one by one.

 

03.07.4. Solution

비어 있는 구멍이 있으면 가릴 것 없이 바로 사용하면 되고 없다면 현재 사용중인 기기 중 가장 사용할 확률이 낮은 기기의 플러그를 뽑고 사용하면 됩니다. 여기서 사용할 확률이 낮은 기기라는 것은 결국 추후에 사용하지 않거나 가장 뒤늦게 사용하는 기기입니다. 만약 가장 뒤늦게 사용하는 기기가 아닌 다른 기기의 플러그를 뽑는다면 그 기기는 뽑지 않기로 선택한 기기보다 앞서 사용되므로 어쨋거나 플러그를 뽑는 동작을 취하게 될 가능성만 높일 것입니다. 우선순위 큐를 이요해도 되겠죠. 머리가 잘 돌아가지 않았을 때 짜서 그런지 코드가 많이 지저분해 보일 수 있습니다. (그래서 다른 문제와 달리 주석을 좀 달아놓았습니다.)

 

	int n, m, i, j;
	scanf("%d %d",&n, &m);
	int data[m], c = 0, check[n] = {0}, c1, order[m+1];
	for(i = 0; i < m; i++){
		scanf("%d", &data[i]);
	}
	int temp, c2;
	for(i = 0; i < m; i++){
		c1 = 1;
		c2 = 0;
		for(j = 0; j < n; j++){
			if(data[i] == check[j]) {
				c1 = 0;//있는 놈이면 
				break;	
			}
			if(check[j] == 0){//빈 콘센트가 있는 경우 
				c2 = j+1;
				break;	
			} 
		}
		if(c1){//콘센트에 안 꽂힌 놈이면 
			if(c2)
				check[c2-1] = data[i]; //빈 콘센트가 있는 경우 
			else{
				//꽉 차 있을 때 : 안나오는 것을 바꾸고 안나오는 것이 없으면 제일 뒤에 나오는 것을 바꾸기
				//수정 : 꽉 차 있을 때 : 제일 먼저 나오는 것으로 바꾸기 제일 먼저 나오는 것이 없으면 안나오는 것을 바꾸기
				/* 
				for(j = 1; j < m+1; j++){
					order[j] = (m+1); // 나오는 순서 초기화 : 안나오면 가장 값이 크도록 설정 
				}
				for(j = n-1; j > i; j--){
					order[data[j]] = j; // 나오는 순서 저장 
				}
				temp = m+1;
				for(j = 0; j < n; j++){
					temp = min(temp, order[check[j]]);
				}
				for(j = 0; j < n; j++){
					if(order[check[j]] == temp){
						check[j] = data[i];
						break;
					}
				}
				*/
				for(j = 1; j < m+1; j++){
					order[j] = 0; // 나오는 순서 초기화 : 안나오면 가장 값이 작도록 설정 
				}
				for(j = m-1; j > i; j--){
					order[data[j]] = j; // 나오는 순서 저장
				}
				temp = 0;
				for(j = 0; j < n; j++){ // 바꿀놈 지정 
					//printf("%d ",order[check[j]]); 
					temp = max(temp, order[check[j]]);
					if(order[check[j]] == 0){
						temp = order[check[j]];
						break;
					}
				}
				//printf("\n");
				for(j = 0; j < n; j++){
					if(order[check[j]] == temp){
						check[j] = data[i];
						break;
					}
				}
				c++;
			}
		}
		//for(j = 0; j < n; j++){
		//	printf("%d ",check[j]);
		//}
		//printf("\n"); 
	}
	printf("%d", c);

아래의 Test Case가 여러분에게 도움이 되면 좋겠습니다.

2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3
>> 2

 

3 14
1 4 3 2 5 4 3 2 5 3 4 2 3 4
>> 4

1
1 4
1 4 3
2 4 3 //더이상 안나오는 것으로 바꿈 
5 4 3 //나오는 것 중에 가장 뒤에 있는 것 선택