03.10. Rest Stops[Greedy Algorithm][백준 15748]

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

15748번: Rest Stops

 

Algorithm classification : Greedy Algorithm, Sorting

 

03.10.1. Problem

Farmer John and his personal trainer Bessie are hiking up Mount Vancowver. For their purposes (and yours), the mountain can be represented as a long straight trail of length L meters. Farmer John will hike the trail at a constant travel rate of r_Fseconds per meter.  Since he is working on his stamina, he will not take any rest stops along the way.

 

Bessie, however, is allowed to take rest stops, where she might find some tasty grass. Of course, she cannot stop just anywhere! There are N rest stops along the trail; the i-th stop is x_i meters from the start of the trail and has a tastiness value c_i. If Bessie rests at stop i for t seconds, she receives c_i * t tastiness units.

 

When not at a rest stop, Bessie will be hiking at a fixed travel rate of r_B seconds per meter. Since Bessie is young and fit, r_B is strictly less than r_P.

 

Bessie would like to maximize her consumption of tasty grass. But she is worried about Farmer John; she thinks that if at any point along the hike she is behind Farmer John on the trail, he might lose all motivation to continue!

 

Help Bessie find the maximum total tastiness units she can obtain while making sure that Farmer John completes the hike.

 

03.10.2. Input limit

 

03.10.3. Output

A single integer: the maximum total tastiness units Bessie can obtain.

 

03.10.4. Solution

결국 우리는 어디서 얼마나 기다릴지 고민하면 됩니다. c의 값에 따라서 더 많은 c를 얻을 수 있는 지점에서 기다리는 것이 이득이겠죠. 동일한 논리로 계속 가다보면 결국 제일 큰 c값을 가지는 지점에서 기다리다가 남은 구간에서 같은 작업을 반복하면 될 것입니다. 범위는 이 문제를 옮기다보면서 생략하였는데 고려해야 할 요소 중 하나입니다. 아래의 코드가 조금 난잡하게 느껴지실 수 있는데 아이디어는 기다릴 수 있는 시간을 어딘가에 계속 누적시키는 것입니다. 마지막에 sum += data[i][3] * data[i][1];를 이해하시면 이해하실 수 있을 겁니다. 중간에 주석처리된 출력문들은 제가 코딩하면서 제대로 된 값들을 출력하는지 알아보기 위함입니다.(메모리를 많이 잡아먹는다는 것이 꼭 나쁜 것만은 아닌 것 같습니다. 이렇게 중간에 값을 출력할 수 있다는 것은 결국 유지보수를 용이하게 하겠죠.)

	int l, n, t1, t2, tu, i;
	scanf("%d %d %d %d", &l, &n, &t1, &t2);
	tu = t1 - t2;
	int data[n][4] = {0};
	for(i = 0; i < n; i++){
		scanf("%d %d", &data[i][0], &data[i][1]);
		data[i][2] = i ? (data[i][0] - data[i-1][0]) * tu : data[i][0] * tu;
	}
	long long int sum = 0, index = n-1;
	int temp = data[n-1][1], j;
	for(i = n-1; i >= 0; i--){
		if(temp >= data[i][1]){
			data[index][3] += data[i][2];
		}
		else{
			temp = max(temp, data[i][1]);
			index = i;
			data[index][3] += data[index][2];
		}
		//printf("%d\n", temp);
	}
	for(i = 0; i < n; i++){
		sum += data[i][3] * data[i][1];
		//printf("%d %d %d\n",data[i][0], data[i][2], data[i][3]);	
	}
	
	printf("%ld", sum);

 

여러분들을 위해 Test case를 남겨둡니다. 도움이 되셨으면 합니다.

10 2 4 3
7 2
8 1
>> 15

이 Case에 대한 hint를 읽어보시면 문제 이해를 빠르게 하실 수 있습니다.

10 2 4 3
7 1
8 2
>>16